LeetCode 291. Word Pattern II | all4win78

LeetCode 291. Word Pattern II | all4win78

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.

Analysis:

很明显，这是一道search的题目，国际惯例，想到用dfs（recursion）搞定。这题目的考点对应关系，很容易想到用HashMap之类的数据结构，<key, value>的选择我建议是<Character, String>，因为在每次检查中，下一个Character是唯一确定的，而对应String的长度则不一定。值得注意的是，本题中pattern = "ab", str = "aa"是false，也就是说pattern中每一个Character和str中每一个substring是一一对应，而不是普通函数的多对一。所以我多用了一个Set来存已经找到对应的substring，以便避开多对一的情况。

Solution:

Read full article from LeetCode 291. Word Pattern II | all4win78