本文共 1663 字，大约阅读时间需要 5 分钟。

题目链接: https://leetcode.com/problems/word-pattern-ii/

Given a pattern and a string str, find if str follows 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.

Examples:

1. pattern = "abab", str = "redblueredblue" should return true.
2. pattern = "aaaa", str = "asdasdasdasd" should return true.
3. pattern = "aabb", str = "xyzabcxzyabc" should return false.

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

思路: 也是很烦的一题. 基本思路是对于pattern字符串来说, 一个字符对应一个字符串, 而对于str来说一个子串对应一个字符. 他们是一一对应的, 因此可以设置两个hash表来映射他们的对应关系. 然后用DFS来搜索对应关系. 一个需要注意的是当回溯的时候如果从当前的字符-字符串的对应开始搜索无法得到正确答案, 不一定要删除他们的对应关系, 因为在之前他们可能是对应的, 如果此时删除了之前的映射虽然实际存在, 但在hash表中已经没有了记录.

代码如下:

class Solution {public:    bool DFS(string& p, int k, string& str, int len)    {        int pLen = p.size(), sLen = str.size();        if(pLen== k && sLen==0)  return true;        if(pLen-k > sLen || pLen == k || sLen==0 || len> sLen) return false;        if(DFS(p, k, str, len+1)) return true;        string left = str.substr(0, len), right = str.substr(len);        int flag = hash1.count(p[k]);        if(hash1.count(p[k]) && hash1[p[k]] != left) return false;        if(hash2.count(left) && hash2[left] != p[k]) return false;        hash1[p[k]] = left, hash2[left] = p[k];        if(DFS(p, k+1, right, 1)) return true;        if(hash1.count(p[k]) != flag)             hash1.erase(p[k]), hash2.erase(left);        return false;    }        bool wordPatternMatch(string pattern, string str) {        return DFS(pattern, 0, str, 1);    }private:    unordered_map
   
     hash1;    unordered_map
    
      hash2;};
    
   

转载地址：http://kglbn.baihongyu.com/