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

Question

我最近在面试中被问到这个问题:

"Given a pattern and a string input - find if the string follows the same pattern and return true or false."

Examples:

1. Pattern : "abba", input: "redbluebluered" should return 1.
2. Pattern: "aaaa", input: "asdasdasdasd" should return 1.
3. Pattern: "aabb", input: "xyzabcxzyabc" should return 0.

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

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

Answer 1

以递归方式执行此操作更容易。

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

// 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;
}

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