匹配String1中String2的字符的出现和模式

Question

我在暑期实习的电话采访中被问到这个问题,并试图在Java中提出一个*m复杂的解决方案(虽然它也不准确).

我有一个需要2个字符串的函数,假设是"common"和"cmn".它应该基于"c","m","n"在"common"中以相同顺序发生的事实返回True.但是如果参数是"common"和"omn",它将返回False,因为即使它们以相同的顺序发生,但是'm'也出现在'o'之后(它不符合模式匹配条件)

我已经使用Hashmaps和Ascii阵列来解决它,但还没有得到令人信服的解决方案!从我读到现在,它可以与Boyer-Moore或Levenshtein距离算法有关吗？

希望在stackoverflow上喘息一下!:)

编辑:一些答案谈论减少字长或创建一个哈希集.但根据我的理解,这个问题不能用hashsets来完成,因为第一个字符串中每个字符的出现/重复都有其自身的意义.通过条件 - "con","cmn","cm","cn","mn","on","co".失败的情况可能看起来不是 - "com","omn","mon","om".这些是FALSE/FAIL,因为"o"发生在"m"之前和之后.另一个例子 - "google","ole"会PASS,但"google","gol"会失败,因为"o"也出现在"g"之前!

Answer 1

我认为这很简单。运行该模式，并在每个字符之前获取它在字符串中最后一次出现的索引。索引必须始终增加，否则返回 false。所以用伪代码来说：

index = -1
foreach c in pattern
    checkindex = string.lastIndexOf(c)
    if checkindex == -1                   //not found
        return false
    if checkindex < index
        return false
    if string.firstIndexOf(c) < index     //characters in the wrong order
        return false
    index = checkindex
return true

编辑：index您可以通过将起始索引传递给方法来进一步改进代码lastIndexOf。那么你就不必进行比较，checkindex并且index算法会更快。

更新：修复了算法中的错误。添加了附加条件来考虑模式中字母的顺序。