剑指Offer: 字符串的排列

客官°小女子只卖身不卖艺 2023-07-18 02:48 117阅读 0赞

##### 1. 题目描述 #####

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

> 输入描述:  
> 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

原题传送门：[link][].

##### 2. 提取关键词 #####

打印字符串

##### 3. 思路 #####

*  牛客网解答链接: [link][link 1].

##### 4. 代码（Java） #####

/**
    import java.util.List;
    import java.util.Collections;
    import java.util.ArrayList;
     
    public class Solution {
        public static void main(String[] args) {
            Solution p = new Solution();
            System.out.println(p.Permutation("abc").toString());
        }
     
        public ArrayList<String> Permutation(String str) {
            List<String> res = new ArrayList<>();
            if (str != null && str.length() > 0) {
                PermutationHelper(str.toCharArray(), 0, res);
                Collections.sort(res);
            }
            return (ArrayList)res;
        }
     
        public void PermutationHelper(char[] cs, int i, List<String> list) {
            if (i == cs.length - 1) {
                String val = String.valueOf(cs);
                if (!list.contains(val))
                    list.add(val);
            } else {
                for (int j = i; j < cs.length; j++) {
                    swap(cs, i, j);
                    PermutationHelper(cs, i+1, list);
                    swap(cs, i, j);
                }
            }
        }
     
        public void swap(char[] cs, int i, int j) {
            char temp = cs[i];
            cs[i] = cs[j];
            cs[j] = temp;
        }
    }

##### 5. 知识积累 #####

暂无

[link]: https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=13&tqId=11180&tPage=2&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking
[link 1]: https://www.nowcoder.com/questionTerminal/fe6b651b66ae47d7acce78ffdd9a96c7?f=discussion