递归打印仅字典上较大的子字符串

Question

我正在编写一段代码，用于递归地只打印字符串的字典序较大的子字符串。

static ArrayList<String> getPermutations(String str) {
    if (str.length() == 0) {
        ArrayList<String> tempArrayList = new ArrayList<String>();
        tempArrayList.add("");
        return tempArrayList;
    }

    char currChar = str.charAt(0);
    ArrayList<String> resultArrayList = new ArrayList<String>();
    ArrayList<String> recResult = getPermutations(str.substring(1));

    for (String j : recResult) {
        for (int i = 0; i < str.length(); i++) {
            resultArrayList.add(j.substring(0, i) + currChar + j.substring(i));
        }
    }
    return resultArrayList;
}

public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    String str = sc.nextLine();
    ArrayList<String> al = getPermutations(str);
    Collections.sort(al);
    // System.out.println(al.toString());
    int index = al.lastIndexOf(str);
    while (index < al.size() - 1) {
        System.out.println(al.get(index + 1));
        index++;
    }
}

代码运行良好。我在这里所做的是递归生成所有子字符串，并同时将它们插入ArrayList。后来对该列表进行排序，比较字符串，瞧，就这样完成了。

现在困扰我的是这个程序的复杂性。在这里，我生成所有的子字符串，然后从中进行选择。对于递归，我觉得这是一个自动化的过程，所有的子字符串都必须至少创建或访问一次。所以，在这一点上，我想问一下这是否可以优化，比如在递归函数中进行某种检查，以便只创建所需的子字符串（字典上更大）。如果可以，那么请详细说明在基于递归的解决方案中如何考虑它。

Answer 1

我会这样做，没有递归，没有额外的字符串构建和忽略，没有输入中重复字母引起的重复。

希望代码中的注释足以理解逻辑。

static List<String> getLargerPermutations(String input) {
    // Build ordered array of unique characters in the input string
    // E.g. "mississippi" -> ['i', 'm', 'p', 's']
    char[] buf = input.toCharArray();
    Set<Character> charSet = new TreeSet<>();
    for (char ch : buf)
        charSet.add(ch);
    Character[] chars = charSet.toArray(Character[]::new);
    
    // Build map of character to index into CharCount array
    // E.g. "mississippi" -> { i=0, m=1, p=2, s=3 }
    Map<Character, Integer> charIndex = new HashMap<>();
    for (int i = 0; i < chars.length; i++)
        charIndex.put(chars[i], i);
    
    // Build position indexes with starting index for input string
    // E.g. "mississippi" -> [1, 0, 3, 3, 0, 3, 3, 0, 2, 2, 0]
    int[] idx = new int[buf.length];
    for (int i = 0; i < buf.length; i++)
        idx[i] = charIndex.get(buf[i]);
    
    // Build permutations by "incrementing" the indexes
    // E.g. "mississippi" -> [1, 0, 3, 3, 0, 3, 3, 0, 2, 2, 0] (starting buffer, not returned)
    //                    -> [1, 0, 3, 3, 0, 3, 3, 2, 0, 0, 2]
    //                    -> [1, 0, 3, 3, 0, 3, 3, 2, 0, 2, 0]
    //                    -> [1, 0, 3, 3, 0, 3, 3, 2, 2, 0, 0]
    //                    -> [1, 0, 3, 3, 2, 0, 0, 0, 2, 3, 3]
    //                    -> [1, 0, 3, 3, 2, 0, 0, 0, 3, 2, 3]
    List<String> permutations = new ArrayList<>();
    int[] counts = new int[chars.length];
    OUTER: for (int i = idx.length - 1; i >= 0; i--) { // keep going backwards to advance character at previous position:
        counts[idx[i]]++;                              //   return character at current position to pool
        while (++idx[i] < chars.length) {              //   try next character at current position:
            if (counts[idx[i]] > 0) {                  //     if character is available:
                counts[idx[i]]--;                      //       take character from pool
                buf[i] = chars[idx[i]];                //       place character in buffer
                i++;                                   //       advance to next position
                if (i == buf.length) {                 //       if buffer full:
                    permutations.add(new String(buf)); //         we have a good permutation
                    continue OUTER;                    //         continue outer loop to advance to next permutation
                }
                idx[i] = -1;                           //       clear search index of next position
            }
        }                                              //   loop back to try next character
    }                                                  // out of characters at current position, so loop back to try previous position
    return permutations;
}

测试

getLargerPermutations("ball").forEach(System.out::println);

带“球”的输出

blal
blla
labl
lalb
lbal
lbla
llab
llba

输出带"Powwow"

powwwo
pwooww
pwowow
pwowwo
pwwoow
pwwowo
pwwwoo
woopww
woowpw
woowwp
wopoww
wopwow
wopwwo
wowopw
wowowp
wowpow
wowpwo
wowwop
wowwpo
wpooww
wpowow
wpowwo
wpwoow
wpwowo
wpwwoo
wwoopw
wwoowp
wwopow
wwopwo
wwowop
wwowpo
wwpoow
wwpowo
wwpwoo
wwwoop
wwwopo
wwwpoo