java - 模式匹配面试 Q

Question

我最近在接受采访，他们问了我以下问题:

Write a function to return true if a string matches a pattern, false otherwise

模式:每个项目 1 个字符，(a-z)，输入:空格分隔字符串

这是我对第一个问题的解决方案:

static boolean isMatch(String pattern, String input) {
    char[] letters = pattern.toCharArray();
    String[] split = input.split("\\s+");

    if (letters.length != split.length) {
        // early return - not possible to match if lengths aren't equal
        return false;
    }

    Map<String, Character> map = new HashMap<>();
    // aaaa test test test1 test1
    boolean used[] = new boolean[26];
    for (int i = 0; i < letters.length; i++) {
        Character existing = map.get(split[i]);
        if (existing == null) {
            // put into map if not found yet
            if (used[(int)(letters[i] - 'a')]) {
                return false;
            }

            used[(int)(letters[i] - 'a')] = true;
            map.put(split[i], letters[i]);
        } else {
            // doesn't match - return false
            if (existing != letters[i]) {
                return false;
            }
        }
    }

    return true;
}

public static void main(String[] argv) {
    System.out.println(isMatch("aba", "blue green blue"));
    System.out.println(isMatch("aba", "blue green green"));
}

问题的下一部分难住了我:

With no delimiters in the input, write the same function.

例如:

isMatch("aba", "bluegreenblue") -> true
isMatch("abc","bluegreenyellow") -> true
isMatch("aba", "t1t2t1") -> true
isMatch("aba", "t1t1t1") -> false
isMatch("aba", "t1t11t1") -> true
isMatch("abab", "t1t2t1t2") -> true
isMatch("abcdefg", "ieqfkvu") -> true
isMatch("abcdefg", "bluegreenredyellowpurplesilvergold") -> true
isMatch("ababac", "bluegreenbluegreenbluewhite") -> true
isMatch("abdefghijklmnopqrstuvwxyz", "zyxwvutsrqponmlkjihgfedcba") -> true

我写了一个蛮力解决方案(生成大小为 letters.length 的输入字符串的所有可能拆分，并依次检查 isMatch)但面试官说它不是t 最优。

我不知道如何解决这部分问题，这甚至可能还是我错过了什么？

他们正在寻找时间复杂度为 O(M x N ^ C) 的东西，其中 M 是模式的长度，N 是输入的长度，C 是某个常数.

澄清

• 我不是在寻找正则表达式解决方案，即使它有效。
• 我不是在寻找一种简单的解决方案，它可以生成所有可能的拆分并检查它们，即使进行了优化，因为这始终是指数级的时间。

Answer 1

可以优化回溯解决方案。我们可以“即时”检查它，而不是先生成所有拆分然后检查它是否有效。假设我们已经拆分了初始字符串的前缀(长度为 p )并匹配了 i模式中的字符。我们来看看i + 1字符。

1. 如果前缀中有字符串对应i + 1字母，我们应该只检查从位置 p + 1 开始的子字符串等于它。如果是，我们就继续 i + 1和 p + the length of this string .否则，我们可以杀死这个分支。

2. 如果没有这样的字符串，我们应该尝试所有从 p + 1 开始的子字符串并在它之后的某个地方结束。

我们还可以使用以下思路来减少您的解决方案中的分支数量:我们可以估计尚未处理的模式的后缀长度(我们知道已经代表某些字母的长度字符串，并且我们知道模式中任何字母的字符串长度的一个微不足道的下限(它是 1))。如果初始字符串的剩余部分太短而无法匹配模式的其余部分，它允许我们终止一个分支。

此解决方案仍然具有指数时间复杂度，但它的工作速度比生成所有拆分要快得多，因为无效的解决方案可以更早地被丢弃，因此可到达状态的数量可以显着减少。