是否有一种有效的算法来输出存储在按字典顺序排序的列表中的所有字符串，这些字符串是输入字符串的排列？

Question

我想找到解决这个问题的最有效的算法： 给定一个字符串 str 和一个仅由小写英文字符组成且按字典顺序排序的字符串列表 lst，找到 中的所有单词>lst 是 str 的排列。

例如： str = "cat", lst = {"aca", "acc", "act", "cta", "tac"}

将返回：{"act" , "cta", "tac"}

我已经有了一个算法，该算法没有利用 lst 按字典顺序排序的事实，并且我正在寻找利用此优势的最有效算法事实。

我的算法是这样的：

public List<String> getPermutations(String str, List<String> lst){
  List<String> res = new ArrayList<>();
  for (String word : lst)
        if (checkPermutation(word, str))
            res.add(word);
  return res;
}


public boolean checkPermutation(String word1, String word2) {
    if (word1.length() != word2.length())
        return false;
    int[] count = new int[26];
    int i;
    for (i = 0; i < word1.length(); i++) {
        count[word1.charAt(i) - 'a']++;
        count[word2.charAt(i) - 'a']--;
    }
    for (i = 0; i < 26; i++)
        if (count[i] != 0) {
            return false;
        }
    return true;
}

总运行时间是 O(NK)，其中 N 是 lst 中的字符串数量，k 是 str 的长度。

Answer 1

一种简单的优化（仅对非常大的数据集才有意义，因为它并没有真正提高 O(NK)：

• 将传入的 str 的所有字符放入 Set strChars< /code>
• 现在：迭代列表中的单词时：获取每个条目的第一个字符
• if strChars.contains(charFromListEntry)：检查它是否是排列
• else：显然，该列表单词可以'是一个排列

注意：排序顺序在这里没有多大帮助：因为您仍然需要检查列表中下一个字符串的第一个字符，

可能还有其他检查 。避免昂贵的 checkPermutation() 运行，例如首先比较单词的长度：当列表字符串比输入字符串短时，它显然不能是 all 的排列 字符

。说，最后你必须迭代列表中的所有条目并确定一个条目是否是排列。没有办法避免相应的“循环”。您唯一可以影响的是循环内发生的成本。

最后：如果您的字符串列表是一个集合，那么您可以“简单地”计算传入的 str 的所有排列，并检查每个排列是否包含在该集合中。但是当然，为了将列表转换为集合，您必须迭代该操作。

Answer 2

您可以迭代字符串的所有排列并使用二分搜索检查列表中的每个元素，而不是迭代列表并检查每个元素是否为字符串的排列。

例如

public List<String> getPermutations(String str, List<String> lst){
    List<String> res = new ArrayList<>();
    perm(str, (1L << str.length()) - 1, new StringBuilder(), lst, res);
    return res;
}

private void perm(String source, long unused,
                  StringBuilder sb, List<String> lst, List<String> result) {
    if(unused == 0) {
        int i = Collections.binarySearch(lst, sb.toString());
        if(i >= 0) result.add(lst.get(i));
    }
    for(long r = unused, l; (l = Long.highestOneBit(r)) != 0; r-=l) {
        sb.append(source.charAt(Long.numberOfTrailingZeros(l)));
        perm(source, unused & ~l, sb, lst, result);
        sb.setLength(sb.length() - 1);
    }
}

，现在时间复杂度为 O(K! × log N)，这不一定比您的方法的 O(NK) 更好。它在很大程度上取决于 K 和 N 的大小。如果字符串非常短并且列表非常大，则它可能具有优势。

有很多可以想象的优化。例如，代替构造每个排列，然后进行二分搜索，每个递归步骤可以进行部分搜索来识别下一步的潜在搜索范围，并在清楚不能包含排列时跳过。虽然这可以显着提高性能，但它不能改变基本的时间复杂度，即最坏的情况。