Java中ArrayList与HashSet实现字谜求解超时问题优化咨询

我正在解决lexicography问题，需求是给定单词和索引，生成该单词的所有字谜并返回指定索引的单词。我的代码功能正常，但运行速度过慢，超出了1秒的时间限制。当前我使用HashSet收集所有字谜以避免重复，再转换为ArrayList进行排序。

原实现代码 #

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Scanner;

public class lexicography {
    
    public static void main(String[] args) {
        
        ArrayList<String> resultat = new ArrayList<>(50);
        Scanner in = new Scanner(System.in);
        
        ArrayList<String> anagramLista;
        HashSet<String> tempLista;
        
        do {
             String ord = in.next();
             int num = in.nextInt();
             
             if(ord.compareTo("#") == 0 && num == 0)
                 break;
             
             tempLista = new HashSet<>(fakultet(ord.length()));
             
             hittaAnagram("", ord, tempLista);
             anagramLista = new ArrayList<>(tempLista);
             Collections.sort(anagramLista);
             
             resultat.add(anagramLista.get(num-1));
             
        }while(true);
        
        in.close();
        
        for(String s: resultat) {
            System.out.println(s);
        }
    }
    
    static int fakultet(int n) {
        
        if(n == 0)
            return 1;
        else
            return n * fakultet(n-1);
    }
    
    static void hittaAnagram(String prefix, String rest, HashSet<String> listan) {
        if(rest.length() == 0) {
            listan.add(prefix);
        } else {
            for(int i = 0; i < rest.length(); i++) {
                
                hittaAnagram(prefix + rest.charAt(i), 
                             rest.substring(0, i) + rest.substring(i + 1), 
                             listan);
            }
        }
    }
}

问题核心原因 #

当前代码的最大问题是生成所有可能的字谜再去重排序，时间复杂度为O(n!)，当单词长度超过8时，n!的数值会急剧增长（比如n=10时，10! = 3628800），即使有重复字符，生成所有排列的过程也会消耗大量时间，HashSet去重和后续排序也会额外增加开销，完全无法在1秒内处理较长的单词。

优化方案（根本性解决超时） #

换数据类型只能带来微小的性能提升，无法解决本质问题。正确的思路是直接计算第k个排列，不需要生成所有字谜：

• 统计字符频率：用数组统计每个字符出现的次数，避免重复处理相同字符。
• 计算带重复的排列数：剩余字符的唯一排列数公式为 剩余长度! / (各字符剩余次数的阶乘乘积)，快速判断当前字符对应的排列区间是否包含目标索引。
• 逐个确定结果字符：按字典序遍历每个字符，计算选择该字符后剩余字符的排列数。如果目标索引小于该数，就确定当前字符，更新字符频率和剩余长度；否则减去该数，继续判断下一个字符。
• 用char数组构建结果：避免String拼接的频繁对象创建，提升效率。

优化后的示例代码 #

import java.util.Scanner;

public class Lexicography {
    private static long[] factorial;

    public static void main(String[] args) {
        // 预计算阶乘，最大支持到20（20!在long范围内）
        factorial = new long[21];
        factorial[0] = 1;
        for (int i = 1; i <= 20; i++) {
            factorial[i] = factorial[i-1] * i;
        }

        Scanner in = new Scanner(System.in);
        while (true) {
            String ord = in.next();
            int num = in.nextInt();
            if (ord.equals("#") && num == 0) break;

            System.out.println(findKthAnagram(ord, num - 1)); // 转为0索引
        }
        in.close();
    }

    private static String findKthAnagram(String s, long k) {
        int[] freq = new int[26];
        int len = s.length();
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }

        char[] result = new char[len];
        for (int pos = 0; pos < len; pos++) {
            for (int i = 0; i < 26; i++) {
                if (freq[i] == 0) continue;

                // 减少当前字符的频率，计算剩余排列数
                freq[i]--;
                long permCount = calculatePermCount(len - pos - 1, freq);
                if (k < permCount) {
                    result[pos] = (char) ('a' + i);
                    break;
                } else {
                    // 不在当前字符的区间，恢复频率，减去当前区间的数量
                    freq[i]++;
                    k -= permCount;
                }
            }
        }
        return new String(result);
    }

    private static long calculatePermCount(int remainingLen, int[] freq) {
        long count = factorial[remainingLen];
        for (int f : freq) {
            if (f > 0) {
                count /= factorial[f];
            }
        }
        return count;
    }
}

关于数据类型调整的效果 #

• char数组替代String拼接：确实能减少大量String对象的创建开销，提升部分效率，但无法解决生成所有排列的本质问题，对于较长单词依然会超时。
• 数组替代List/HashSet：只能减少集合操作的额外开销，但生成所有排列的O(n!)时间复杂度依然是瓶颈，无法满足时间限制。

内容的提问来源于stack exchange，提问作者Mårten Ask