【剑指offer-Java版】28字符串的排列

你的名字 2022-08-21 09:40 167阅读 0赞

字符串的全排列：全排列问题刚刚做过，而且解决方法不止一种

递归，多想想

public class _Q28<T> {
    
        private int count = 0;
    
        public void Premutation(char chars[], int begin){
            if(chars == null) return;
    
            if(chars.length == 0 || begin < 0) return;
    
            int end = chars.length - 1;
            if(begin == end){
                count++;
                System.out.print(count+" : ");
                System.out.println(chars);
            }else{
                for(int i=begin; i<=end; i++){
                    char c = chars[begin]; // 第一步，找出所有可以出现在首位的字符
                    chars[begin] = chars[i];
                    chars[i] = c;
    
                    Premutation(chars, begin+1); // 第二步，递归的求出后半部分的全排列
    
                    c = chars[begin];
                    chars[begin] = chars[i]; // 第一步的后半部分，恢复数组
                    chars[i] = c;
                }
            }
        }
    
        /**
         * 
         * @comment TODO
         * @param chars 
         * @param m 排列的长度 -- 如果需要输出指定字符数组的全排列，那么直接使用for循环，使m 从0到数组长度即可
         * @param result   排列结果链表
         * @return void  
         * @throws
         * @date 2016年4月16日 下午4:20:57
         */
        public void Combination(char chars[], int m, List<Character> result){
    
            if(chars == null || result == null) return;
    
            if(m == 0){
                System.out.println(result);
                return;
            }
    
            if(chars.length > 0){
                // 包含当前第一个字符 -- 从剩下的字符中选出 m-1个
                result.add(chars[0]);
                Combination(Arrays.copyOfRange(chars, 1, chars.length), m-1, result);
    
                // 不包含当前第一个字符 -- 从剩下的字符中选出m 个
                result.remove(result.size()-1);
                Combination(Arrays.copyOfRange(chars, 1, chars.length), m, result);
            } 
    
        }
        }

测试代码

public class _Q28Test extends TestCase {
        
    
        _Q28 premutation = new _Q28();
    
        public void test(){
            String str = "abcd";
            char chars[] = str.toCharArray();
    
            premutation.Premutation(chars, 0);
    
            List<Character> result = new ArrayList<>();
            premutation.Combination(chars, 2, result);
        }
        }