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

1. 题目

给你一种规律 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 都只会包含小写字母。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/word-pattern-ii

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

class Solution {
   	unordered_map
   
     m;    unordered_map
    
      str_char;	bool match = false;public:    bool wordPatternMatch(string pattern, string str) {
           dfs(pattern, str, 0, 0);        return match;    }    void dfs(string& pattern, string& str, int i, int j)    {
       	if((i < pattern.size() && j >= str.size())    		|| (i >= pattern.size() && j < str.size()) || match)    		return;    	if(i == pattern.size() && j == str.size())    	{
       		match = true;    		return;    	}    	if(!m.count(pattern[i]))    	{
       		string val;    		for(int k = 1; k <= str.size()-j; ++k)//该字符往后匹配多少个字符    		{
       			val = str.substr(j, k);                if(str_char.count(val) && str_char[val] != pattern[i])//"ab"，"aa"                    continue;    			m[pattern[i]] = val;                str_char[val] = pattern[i];    			dfs(pattern, str, i+1, j+k);    			m.erase(pattern[i]);                str_char.erase(val);    		}    	}    	else    	{
       		string val = m[pattern[i]];    		int n = val.size();    		if(str.substr(j, n) != val)    			return;    		dfs(pattern, str, i+1, j+n);    	}    }};
    
   

628 ms 52.5 MB

我的CSDN

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

转载地址：https://michael.blog.csdn.net/article/details/107973244 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！