java - 没有正则表达式的单词模式

我最近在一次采访中被问到这个问题:



我可以考虑使用正则表达式，但我们需要在没有正则表达式的情况下执行此操作。在没有正则表达式的情况下执行此操作的蛮力方法是什么，有没有更有效的方法？

如果是的话，有人可以详细解释一下 蛮力 vs 解决这个问题的有效方法吗？在我看来，这是一个相当困难的问题。

最佳答案

递归地执行此操作更容易。

在每一步，我们都有一个要匹配的模式，要匹配的字符串以及我们已经分配的字符到字符串的映射:

// initially, map should be empty.  if this method returns true,
// map will contained the successful char-to-string mapping
boolean solve(String ptrn, String str, Map<Character, String> map) {
    // if pattern is empty, string must also be empty
    if (ptrn.length() == 0) {
        return str.length() == 0;
    }

    char c = ptrn.charAt(0);
    if (map.containsKey(c)) {
        // first char of the pattern is alrady assigned
        // the string must begin with the mapped substring
        String substitution = map.get(c);
        if (str.startsWith(substitution)) {
            // chop off the assigned substring and try to match the rest of the string
            return solve(ptrn.substring(1), str.substring(substitution.length()), map);
        } else {
            // the current assignment map is impossible.  fail!
            return false;
        }
    }

    // first char of the pattern is not assigned
    // loop over the string and try assigning substrings
    for (int i = 1; i <= str.length(); i++) {
        // assign new mapping and try to parse with the new assignment in place
        map.put(c, str.substring(0, i));
        if (solve(ptrn, str, map)) {
            return true;
        }
        // assignment failed.  remove it.
        map.remove(c);
    }
    return false;
}

当然，这可以通过对索引而不是子字符串进行操作并用循环替换一些递归来提高效率。

关于java - 没有正则表达式的单词模式，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53626208/