Word Pattern II 解答

Question

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.

Solution

Word Pattern 是用HashMap的containsKey()和containsValue()两个方法实现的。

但是对于Word Pattern II，我们并不知道怎样划分str，所以基本想法是“暴力搜索”即backtracking/DFS。这里DFS的存储对象不是常见的list，而是map.

 public class Solution {

     public boolean wordPatternMatch(String pattern, String str) {

         return helper(pattern, 0, str, 0, new HashMap<Character, String>());

     }

     private boolean helper(String pattern, int startP, String str, int startS, Map<Character, String> map) {

         if (startP == pattern.length() && startS == str.length()) {

             return true;

         } else if (startP == pattern.length()) {

             }

             if (match.equals(str.substring(startS, endS))) {

                 return helper(pattern, startP + 1, str, endS, map);

             } else {

                 return false;

             }

         } else {

             // If map does not have existing key

             // Traverse, brute force

             for (int i = startS + 1; i <= str.length(); i++) {

                 String candidate = str.substring(startS, i);

                 if (map.containsValue(candidate)) {

                     continue;

                 }

                 map.put(key, candidate);

                 if (helper(pattern, startP + 1, str, i, map)) {

                     return true;

                 }

                 map.remove(key);

             }

         }

         return false;

     }

 }

巴特西

Word Pattern II 解答

Question

Solution

最新文章

热门文章