题目：
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:
- pattern =
"abab", str ="redblueredblue"should return true. - pattern =
"aaaa", str ="asdasdasdasd"should return true. - pattern =
"aabb", str ="xyzabcxzyabc"should return false.
Notes:
You may assume both pattern and str contains only lowercase letters.
链接： http://leetcode.com/problems/word-pattern-ii/
题解：
题目跟Word Pattern基本一样，但输入str里面没有delimiter，所以我们要使用Backtracking来做。因为上一题使用了两个map，所以这一题延续使用，结果给自己造成了很大的困难，代码也写的长而难懂。二刷一定要好好研究backtracking，争取也写出简洁漂亮的代码。
Time Complexity - O(2n)， Space Complexity - O(2n)
public class Solution {
public boolean wordPatternMatch(String pattern, String str) {
if(pattern.length() == 0 && str.length() == 0) {
return true;
}
if(pattern.length() == 0 || str.length() == 0) {
return false;
}
Map<Character, String> patternToStr = new HashMap<>();
Map<String, Character> strToPattern = new HashMap<>();
return wordPatternMatch(pattern, str, patternToStr, strToPattern, 0, 0);
}
private boolean wordPatternMatch(String pattern, String str, Map<Character, String> patternToStr, Map<String, Character> strToPattern, int posPattern, int posString) {
if(posPattern == pattern.length()) {
return true;
}
if(str.length() == 0 && posPattern < pattern.length()) {
return false;
}
int i = 0;
for(i = posString; i < str.length(); i++) {
String word = str.substring(posString, i + 1);
if(posPattern >= pattern.length()) {
return false;
}
char c = pattern.charAt(posPattern);
if(!patternToStr.containsKey(c) && !strToPattern.containsKey(word)) {
patternToStr.put(c, word);
strToPattern.put(word, c);
if(wordPatternMatch(pattern, str.substring(i + 1), patternToStr, strToPattern, posPattern + 1, 0)) {
return true;
}
patternToStr.remove(c);
strToPattern.remove(word);
} else if(patternToStr.containsKey(c) && !word.equals(patternToStr.get(c))) {
if(word.length() == patternToStr.get(c).length()) {
return false;
}
} else if(strToPattern.containsKey(word) && c != strToPattern.get(word)) {
} else {
posPattern++;
posString += word.length();
}
}
return posPattern == pattern.length() ? true: false;
}
}
Reference:
https://leetcode.com/discuss/63252/share-my-java-backtracking-solution
https://leetcode.com/discuss/63393/20-lines-java-clean-solution-easy-to-understand
https://leetcode.com/discuss/63583/20-lines-concise-java-solution-with-explanation
https://leetcode.com/discuss/63724/super-easy-understand-backtracking-java-solution