剑指 Offer 38. 字符串的排列

曾经终败给现在 2024-03-26 14:11 51阅读 0赞

### 剑指 Offer 38. 字符串的排列 ###

![在这里插入图片描述][22b1689f31b14a669bc8f8423380bd87.png]  
一眼回溯

class Solution {
        
        public String[] permutation(String s) {
        
    
            char[] c = s.toCharArray();
            used = new int[c.length];
            Arrays.sort(c);
            find(c,0);
            String[] str = new String[list.size()];
            return list.toArray(str);
            
        }
    
        private void find(char[] chars,int index){
        
            if(index == chars.length){
        
                list.add(sb.toString());
                return;
            }
    
            for(int i=0;i<chars.length;i++){
        
                if(used[i] == 1){
        
                    continue;
                }
                if(i>0 && chars[i] == chars[i-1] && used[i-1]==0){
        
                    continue;
                }
                sb.append(chars[i]);
                used[i]=1;
                find(chars,index+1);
                used[i]=0;
                sb.deleteCharAt(sb.length()-1);
            }
        }
    
        private List<String> list = new ArrayList<String>();
        int[] used;
        private StringBuilder sb = new StringBuilder();
    }

同时还有交换数组元素，来实现生成所有排列的方法  
![在这里插入图片描述][0d3cb5e245f74c558c116fb0a261b025.png]  
比如在这个时候，就只能使用该方法

class Solution {
        
        public String[] permutation(String s) {
        
            char[] c = s.toCharArray();
            find(c,0);
            return list.toArray(new String[list.size()]); 
        }
    
        // 通过不停的交换来获取全排列
        private void find(char[] chars,int index){
        
            if(index == chars.length-1){
        
                list.add(String.valueOf(chars));
                return;
            }
    
            //为了防止同一层递归出现重复元素
            Set<Character> set = new HashSet();
            for(int i=index;i<chars.length;i++){
        
                if(set.contains(chars[i])){
        
                    continue;
                }
                set.add(chars[i]);
                swap(chars,index,i);
                find(chars,index+1);
                swap(chars,index,i);
            }
        }
    
        private void swap(char[] chars, int a, int b){
        
            char temp = chars[a];
            chars[a] = chars[b];
            chars[b] = temp;
        }
    
       
        private List<String> list = new ArrayList<String>();
    }

交换没太明白，后续有时间会仔细研究一波，先记录下

[22b1689f31b14a669bc8f8423380bd87.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/4ee8011d67614420bcd6392f239c3af8.png
[0d3cb5e245f74c558c116fb0a261b025.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/5febd045bc704e51aa009704860b6ceb.png