[LeetCode] Word Pattern II 词语模式之二

Given a pattern and a string str, find if strfollows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.

Example 1:

Input: pattern = "abab", str = "redblueredblue"

Output: true

Example 2:

Input: pattern = pattern = "aaaa", str = "asdasdasdasd"

Output: true

Example 3:

Input: pattern = "aabb", str = "xyzabcxzyabc"

Output: false

Notes:
You may assume both pattern and str contains only lowercase letters.

这道题是之前那道 Word Pattern 的拓展，之前那道题词语之间都有空格隔开，这样可以一个单词一个单词的读入，然后来判断是否符合给定的特征，而这道题没有空格了，那么难度就大大的增加了，因为我们不知道对应的单词是什么，所以得自行分开，可以用回溯法来生成每一种情况来判断，这里还是需要用 HashMap 来建立模式字符和单词之间的映射，还需要用变量p和r来记录当前递归到的模式字符和单词串的位置，在递归函数中，如果p和r分别等于模式字符串和单词字符串的长度，说明此时匹配成功结束了，返回 ture，反之如果一个达到了而另一个没有，说明匹配失败了，返回 false。如果都不满足上述条件的话，取出当前位置的模式字符，然后从单词串的r位置开始往后遍历，每次取出一个单词，如果模式字符已经存在 HashMap 中，而且对应的单词和取出的单词也相等，那么再次调用递归函数在下一个位置，如果返回 true，那么就返回 true。反之如果该模式字符不在 HashMap 中，要看有没有别的模式字符已经映射了当前取出的单词，如果没有的话，建立新的映射，并且调用递归函数，注意如果递归函数返回 false 了，要在 HashMap 中删去这个映射，参见代码如下：

解法一：

class Solution {

public:

    bool wordPatternMatch(string pattern, string str) {

        unordered_map<char, string> m;

        return helper(pattern, , str, , m);

    }

    bool helper(string pattern, int p, string str, int r, unordered_map<char, string> &m) {

        if (p == pattern.size() && r == str.size()) return true;

        if (p == pattern.size() || r == str.size()) return false;

        char c = pattern[p];

        for (int i = r; i < str.size(); ++i) {

            string t = str.substr(r, i - r + );

            if (m.count(c) && m[c] == t) {

                if (helper(pattern, p + , str, i + , m)) return true;

            } else if (!m.count(c)) {

                bool b = false;

                for (auto it : m) {

                    if (it.second == t) b = true;

                }

                if (!b) {

                    m[c] = t;

                    if (helper(pattern, p + , str, i + , m)) return true;

                    m.erase(c);

                }

            }

        }

        return false;

    }

};

下面这种方法和上面那种方法很类似，不同点在于使用了 set，而使用其的原因也是为了记录所有和模式字符建立过映射的单词，这样就不用每次遍历 HashMap 了，只要在 set 中查找取出的单词是否存在，如果存在了则跳过后面的处理，反之则进行和上面相同的处理，注意还要在 set 中插入新的单词，最后也要同时删除掉，参见代码如下：

解法二：

class Solution {

public:

    bool wordPatternMatch(string pattern, string str) {

        unordered_map<char, string> m;

        unordered_set<string> st;

        return helper(pattern, , str, , m, st);

    }

    bool helper(string pattern, int p, string str, int r, unordered_map<char, string> &m, unordered_set<string> &st) {

        if (p == pattern.size() && r == str.size()) return true;

        if (p == pattern.size() || r == str.size()) return false;

        char c = pattern[p];

        for (int i = r; i < str.size(); ++i) {

            string t = str.substr(r, i - r + );

            if (m.count(c) && m[c] == t) {

                if (helper(pattern, p + , str, i + , m, st)) return true;

            } else if (!m.count(c)) {

                if (st.count(t)) continue;

                m[c] = t;

                st.insert(t);

                if (helper(pattern, p + , str, i + , m, st)) return true;

                m.erase(c);

                st.erase(t);

            }

        }

        return false;

    }

};

再来看一种不写 helper 函数的解法，可以调用自身，思路和上面的方法完全相同，参见代码如下：

解法三：

class Solution {

public:

    bool wordPatternMatch(string pattern, string str) {

        if (pattern.empty()) return str.empty();

        if (m.count(pattern[])) {

            string t = m[pattern[]];

            if (t.size() > str.size() || str.substr(, t.size()) != t) return false;

            if (wordPatternMatch(pattern.substr(), str.substr(t.size()))) return true;

        } else {

            for (int i = ; i <= str.size(); ++i) {

                if (st.count(str.substr(, i))) continue;

                m[pattern[]] = str.substr(, i);

                st.insert(str.substr(, i));

                if (wordPatternMatch(pattern.substr(), str.substr(i))) return true;

                m.erase(pattern[]);

                st.erase(str.substr(, i));

            }

        }

        return false;

    }

    unordered_map<char, string> m;

    unordered_set<string> st;

};