LeetCode刷题实战291：单词规律II-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 单词规律II，我们先来看题面：

https://leetcode-cn.com/problems/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.

给你一种规律 pattern 和一个字符串 str，请你判断 str 是否遵循其相同的规律。

这里我们指的是完全遵循，例如 pattern 里的每个字母和字符串 str 中每个非空单词之间，存在着双向连接的对应规律。

示例

示例1:
输入: pattern = "abab", str = "redblueredblue"
输出: true

示例2:
输入: pattern = "aaaa", str = "asdasdasdasd"
输出: true

示例3:
输入: pattern = "aabb", str = "xyzabcxzyabc"
输出: false

提示：
你可以默认 pattern 和 str 都只会包含小写字母。

解题

https://www.cnblogs.com/grandyang/p/5325761.html

这道题是之前那道 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, 0, str, 0, 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 + 1);
            if (m.count(c) && m[c] == t) {
                if (helper(pattern, p + 1, str, i + 1, 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 + 1, str, i + 1, m)) return true;
                    m.erase(c);
                }
            }
        }
        return false;
    }
};