我在暑期实习的电话采访中被问到这个问题,并试图在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"之前!