首页 > 代码库 > LeetCode-Word Pattern II
LeetCode-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:
- 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.
Analysis:
Use recursion, similar to Word Search.
An important optimization:
https://discuss.leetcode.com/topic/36076/java-hashset-backtracking-2ms-beats-100/2
Solution:
public class Solution { public boolean wordPatternMatch(String pattern, String str) { HashSet<String> assigned = new HashSet<String>(); String[] map = new String[26]; Arrays.fill(map,""); return wordPatternMatchRecur(pattern,str,0,0,assigned,map); } public boolean wordPatternMatchRecur(String pattern, String str, int pIndex, int sIndex, HashSet<String> assigned, String[] map){ if (pIndex == pattern.length()){ return sIndex==str.length(); } if (sIndex==str.length()){ return pIndex==pattern.length(); } char code = pattern.charAt(pIndex); boolean matched = false; if (map[code-‘a‘].isEmpty()){ // IMPORTANT OPTIMIZATION: the possible word for current code cannot go beyond a certain boundary, i.e., we need to leave enough length for the following pattern. int endPoint = str.length(); for (int i=pattern.length()-1;i>pIndex;i--){ endPoint -= (map[pattern.charAt(i)-‘a‘].isEmpty()) ? 1 : map[pattern.charAt(i)-‘a‘].length(); } // Try to assign a word to current code. for (int i=sIndex;i<endPoint;i++){ String word = str.substring(sIndex,i+1); if (assigned.contains(word)) continue; map[code-‘a‘] = word; assigned.add(word); if (wordPatternMatchRecur(pattern,str,pIndex+1,i+1,assigned,map)) return true; assigned.remove(word); map[code-‘a‘] = ""; } return false; } else { // Match code.word with the following str. String word = map[code-‘a‘]; if (word.length() > str.length()-sIndex) return false; for (int i=0;i<word.length();i++) if (word.charAt(i) != str.charAt(sIndex+i)){ return false; } // If matched, move to next. matched = wordPatternMatchRecur(pattern,str,pIndex+1,sIndex+word.length(),assigned,map); return matched; } }}
LeetCode-Word Pattern II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。