如何查找给定文本中给定单词的所有排列？

Question

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

我会回答这个问题如下:

• 显然,我可以遍历给定单词的所有排列并使用标准substring函数.但是(现在对我来说)编写代码以生成所有单词排列可能很困难.

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

• 我可以修改一些子串搜索算法,但我现在不记得这些算法了.

你会如何回答这个问题？

Answer 1

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

我们可以说,如果一个单词包含相同数字的相同字母,则该单词是另一个单词的排列.这意味着您可以将单词从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提出的改进

通过以"滚动"方式更新Map可以改进这种方法.

即如果您i=3在OP(子字符串xya)中的示例haystack中的索引处匹配,则映射将为[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)

Answer 2

要查找字符串的排列,您可以使用数论.但是,在使用此算法回答问题之前,您必须事先知道此算法背后的"理论".

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

哈希值由c ₁*p ₁ + c ₂*p ₂ + ... + c _n*p _n计算 ,其中c _i是字符串中当前char的唯一值,其中p _i是唯一素数c _i char的数字值.

这是实施.

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