[LeetCode] Word Pattern II-阿里云开发者社区

[LeetCode] Word Pattern II

2015-10-12 759

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Problem Description: 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 bi...

Problem Description:

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.

The problem becomes much more difficult after the spaces are removed. Now we need to determine which part matchs which part by ourselves. This post shares a very clear solution in Java, which is rewritten below in C++.

 1 class Solution {
 2 public:
 3     bool wordPatternMatch(string pattern, string str) {
 4         unordered_set<string> st;
 5         unordered_map<char, string> mp;
 6         return match(str, 0, pattern, 0, st, mp);
 7     }
 8 private:
 9     bool match(string& str, int i, string& pat, int j, unordered_set<string>& st, unordered_map<char, string>& mp) {
10         int m = str.length(), n = pat.length();
11         if (i == m && j == n) return true;
12         if (i == m || j == n) return false;
13         char c = pat[j];
14         if (mp.find(c) != mp.end()) {
15             string s = mp[c];
16             int l = s.length();
17             if (s != str.substr(i, l)) return false;
18             return match(str, i + l, pat, j + 1, st, mp);
19         } 
20         for (int k = i; k < m; k++) {
21             string s = str.substr(i, k - i + 1);
22             if (st.find(s) != st.end()) continue;
23             st.insert(s);
24             mp[c] = s;
25             if (match(str, k + 1, pat, j + 1, st, mp)) return true;
26             st.erase(s);
27             mp.erase(c);
28         }
29         return false;
30     }
31 };