10

这是一个面试问题（电话屏幕）：编写一个函数（用 Java 编写）来查找给定文本中出现的给定单词的所有排列。例如，对于 wordabc和 text abcxyaxbcayxycab，函数应该返回abc, bca, cab.

我会这样回答这个问题：

  • 显然，我可以遍历给定单词的所有排列并使用标准substring函数。然而，编写代码来生成所有单词排列可能很困难（对我来说现在）。

  • 遍历单词大小的所有文本子字符串，对每个子字符串进行排序并将其与“排序”的给定单词进行比较更容易。我可以立即编写这样的函数。

  • 我可能可以修改一些子字符串搜索算法，但我现在不记得这些算法了。

你会如何回答这个问题？

4

6 回答 6

12

从算法上讲，这可能不是最有效的解决方案，但从类设计的角度来看，它是干净的。该解决方案采用比较“排序”给定单词的方法。

如果一个单词包含相同数字中的相同字母，我们可以说它是另一个单词的排列。这意味着您可以将单词从 a 转换String为 a Map<Character,Integer>。这种转换将具有复杂性 O(n)，其中 n 是 的长度String，假设您的Map实现中的插入成本为 O(1)。

它将包含在单词中找到的所有字符作为键，Map并将字符的频率作为值。

例子。abbc 转换为[a->1, b->2, c->1]

bacb 转换为[a->1, b->2, c->1]

因此，如果您必须知道两个单词是否是另一个单词的排列，您可以将它们都转换为映射，然后调用Map.equals.

然后，您必须遍历文本字符串并将转换应用于您要查找的单词长度相同的所有子字符串。

Inerdial 提出的改进

这种方法可以通过以“滚动”方式更新地图来改进。

即，如果您在i=3OP 中的示例 haystack 中的索引处匹配（子字符串xya），则地图将为[a->1, x->1, y->1]. 在大海捞针中前进时，减少 的字符数haystack[i]，增加 的字符数haystack[i+needle.length()]。

（删除零以确保Map.equals()有效，或者只是实现自定义比较。）

Max 提出的改进

如果我们也引入matchedCharactersCnt变量呢？在干草堆的开始它将是0。每次您将地图更改为所需值时 - 您都会增加变量。每次您将其更改为偏离所需值时 - 您都会减少变量。每次迭代检查变量是否等于针的长度。如果是 - 您已经找到了匹配项。它会比每次比较完整的地图要快。

Max提供的伪代码：

needle = "abbc"
text = "abbcbbabbcaabbca"

needleSize = needle.length()
//Map of needle character counts
targetMap = [a->1, b->2, c->1]

matchedLength = 0
curMap = [a->0, b->0, c->0]
//Initial map initialization
for (int i=0;i<needle.length();i++) {
    if (curMap.contains(haystack[i])) {
        matchedLength++
        curMap[haystack[i]]++
    }
}

if (matchedLength == needleSize) {
    System.out.println("Match found at: 0");
}

//Search itself
for (int i=0;i<haystack.length()-needle.length();i++) {
    int targetValue1 = targetMap[haystack[i]]; //Reading from hashmap, O(1)
    int curValue1 = curMap[haystack[i]]; //Another read
    //If we are removing beneficial character
    if (targetValue1 > 0 && curValue1 > 0 && curValue1 <= targetValue1) {       
        matchedLength--;
    }
    curMap[haystack[i]] = curValue1 + 1; //Write to hashmap, O(1)


    int targetValue2 = targetMap[haystack[i+needle.length()]] //Read
    int curValue2 = curMap[haystack[i+needle.length()]] //Read
    //We are adding a beneficial character
    if (targetValue2 > 0 && curValue2 < targetValue2) { //If we don't need this letter at all, the amount of matched letters decreases
        matchedLength++;
    }
    curMap[haystack[i+needle.length()]] = curValue2 + 1; //Write

    if (matchedLength == needleSize) {
        System.out.println("Match found at: "+(i+1));
    }
}

//Basically with 4 reads and 2 writes which are 
//independent of the size of the needle,
//we get to the maximal possible performance: O(n)
于 2012-05-23T20:42:12.887 回答
5

要找到字符串的排列，您可以使用数论。但是您必须提前了解该算法背后的“理论”，然后才能使用该算法回答问题。

有一种方法可以使用素数计算字符串的哈希值。相同字符串的每个排列都会给出相同的哈希值。所有其他不是排列的字符串组合将给出一些其他哈希值。

哈希值由 c 1 * p 1 + c 2 * p 2 + ... + c n * p n计算 ，其中 c i是字符串中当前字符的唯一值，其中 p i是唯一素数c i字符的数值。

这是实现。

public class Main {
    static int[] primes = new int[] { 2, 3, 5, 7, 11, 13, 17, 
        19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 
        73, 79, 83, 89, 97, 101, 103 };

    public static void main(String[] args) {        
        final char[] text = "abcxaaabbbccyaxbcayaaaxycab"
            .toCharArray();     
        char[] abc = new char[]{'a','b','c'};       
        int match = val(abc);                   
        for (int i = 0; i < text.length - 2; i++) {
            char[] _123 = new char[]{text[i],text[i+1],text[i+2]};          
            if(val(_123)==match){
                System.out.println(new String(_123) );      
            }
        }
    }   
    static int p(char c) {
        return primes[(int)c - (int)'a'];
    }   
    static int val(char[] cs) {
        return 
        p(cs[0])*(int)cs[0] + p(cs[1])*(int)cs[1] + p(cs[2])*(int)cs[2];        
    }
}

它的输出是： abc bca cab

于 2012-05-24T21:38:47.053 回答
3

您应该能够一次完成此操作。首先构建一个包含您要搜索的单词中所有字符的地图。所以最初地图包含[a, b, c].

现在，一次一个字符地浏览文本。在伪代码中，循环看起来像这样。

found_string = "";
for each character in text
    if character is in map
        remove character from map
        append character to found_string
        if map is empty
            output found_string
            found_string = ""
            add all characters back to map
        end if
    else
        // not a permutation of the string you're searching for
        refresh map with characters from found_string
        found_string = ""
    end if
end for

如果您想要唯一的匹配项，请更改输出步骤，以便将找到的字符串添加到地图中。这将消除重复。

存在包含重复字母的单词的问题。如果这是一个问题，请将键作为字母，将值作为计数。“移除”一个角色意味着减少它在地图中的数量。如果计数变为 0，则该角色实际上已从地图中移除。

所写的算法不会找到重叠的事件。也就是说，给定文本abcba，它只会找到abc. 如果要处理重叠事件，可以修改算法，以便在找到匹配项时，将索引减一减去找到的字符串的长度。

那是一个有趣的谜题。谢谢。

于 2012-05-23T21:34:17.840 回答
1

第二种方法对我来说似乎很优雅，应该完全可以接受。我认为它的比例是O(M * N log N)，其中N是字长和M文本长度。

我可以想出一个更复杂的O(M)算法：

  1. 计算单词中每个字符的出现次数
  2. 对文本的前 N（即length(word)）个字符执行相同的操作
  3. 减去两个频率向量，得到subFreq
  4. 计算 中非零的数量subFreq，产生numDiff
  5. 如果numDiff等于 0，则存在匹配
  6. 通过更新文本中的第一个和最后一个字符来更新subFreq并在恒定时间内更新numDiff
  7. 转到 5 直到到达文本的末尾

编辑：看到已经发布了几个类似的答案。该算法的大部分等效于其他人建议的滚动频率计数。我卑微的补充还以滚动方式更新差异的数量，产生一种O(M+N)算法而不是一个算法O(M*N)。

EDIT2：刚刚看到Max在评论中基本上提出了这个建议，所以布朗尼指向他。

于 2012-05-23T21:48:52.910 回答
1

这段代码应该可以完成工作：

import java.util.ArrayList;
import java.util.List;

public class Permutations {
    public static void main(String[] args) {
        final String word = "abc";
        final String text = "abcxaaabbbccyaxbcayxycab";
        List<Character> charsActuallyFound = new ArrayList<Character>();
        StringBuilder match = new StringBuilder(3);

        for (Character c : text.toCharArray()) {
            if (word.contains(c.toString()) && !charsActuallyFound.contains(c)) {
                charsActuallyFound.add(c);
                match.append(c);
                if (match.length()==word.length())
                {
                    System.out.println(match);
                    match = new StringBuilder(3);
                    charsActuallyFound.clear();
                }
            } else {
                match = new StringBuilder(3);
                charsActuallyFound.clear();
            }
        }
    }
}

charsActuallyFound 列表用于跟踪已在循环中找到的字符。需要避免数学运算“aaa”“bbb”“ccc”（由我添加到您指定的文本中）。

经过进一步思考，我认为我的代码只有在给定单词没有重复字符的情况下才有效。上面的代码正确打印

abc
bca
cab

但是如果您搜索“aaa”这个词，则不会打印任何内容，因为每个字符不能匹配超过一次。受 Jim Mischel 回答的启发，我编辑了我的代码，并以此结尾：

import java.util.ArrayList;
import java.util.List;

public class Permutations {
    public static void main(String[] args) {
        final String text = "abcxaaabbbccyaxbcayaaaxycab";

        printMatches("aaa", text);
        printMatches("abc", text);
    }

    private static void printMatches(String word, String text) {
        System.out.println("matches for "+word +" in "+text+":");

        StringBuilder match = new StringBuilder(3);
        StringBuilder notYetFounds=new StringBuilder(word);

        for (Character c : text.toCharArray()) {
            int idx = notYetFounds.indexOf(c.toString());
            if (idx!=-1) {
               notYetFounds.replace(idx,idx+1,"");

                match.append(c);
                if (match.length()==word.length())
                {
                    System.out.println(match);
                    match = new StringBuilder(3);
                    notYetFounds=new StringBuilder(word);
                }
            } else {
                match = new StringBuilder(3);
                notYetFounds=new StringBuilder(word);
            }
        }
        System.out.println();
    }

}

这给了我以下输出：

matches for aaa in abcxaaabbbccyaxbcayaaaxycab:
aaa
aaa

matches for abc in abcxaaabbbccyaxbcayaaaxycab:
abc
bca
cab

做了一些基准测试，上面的代码在 4.5 秒内在 36M 的随机字符串中找到了 30815 个“abc”匹配项。正如吉姆已经说过的，感谢这个谜题......

于 2012-05-23T22:05:28.953 回答
1

这就是我要做的 - 设置一个标志数组，其中一个元素等于 0 或 1，以指示 STR 中的该字符是否已匹配

将第一个结果字符串 RESULT 设置为空。

对于 TEXT 中的每个字符 C：

将等于 STR 长度的数组 X 设置为全零。

对于 STR 中的每个字符 S：如果 C 是 STR 中的第 JTH 个字符，并且 X[J] == 0，则设置 X[J] <= 1 并将 C 添加到 RESULT。如果 RESULT 的长度等于 STR，则将 RESULT 添加到排列列表中，并将 X[] 的元素再次设置为零。

如果 C 不是 STR 中具有 X[J]==0 的任何字符 J，则再次将 X[] 的元素设置为零。

于 2012-05-23T21:34:24.637 回答