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:

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.

Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

public class Solution {     public boolean wordPatternMatch(String pattern, String str) {         if ((pattern == null || pattern.length() == 0) && (str == null || str.length() == 0)) {             return true;         }                   if ((pattern == null || pattern.length() == 0) || (str == null || str.length() == 0)) {             return false;         }                   Map<Character, String> forwardMap = new HashMap<>();         Map<String, Character> invertedMap = new HashMap<>();                   return wordPatternMatchHelper(0, pattern, 0, str, forwardMap, invertedMap);     }           private boolean wordPatternMatchHelper(int pStart, String pattern,                                       int sStart, String str,                                       Map<Character, String> forwardMap,                                       Map<String, Character> invertedMap) {         if (pStart == pattern.length() && sStart == str.length()) {             return true;         }                   if (pStart >= pattern.length() || sStart >= str.length()) {             return false;         }                   char pChar = pattern.charAt(pStart);         for (int i = sStart; i < str.length(); i++) {             String curr = str.substring(sStart, i + 1);                           if ((!forwardMap.containsKey(pChar)) && (!invertedMap.containsKey(curr))) {                 forwardMap.put(pChar, curr);                 invertedMap.put(curr, pChar);                                   if (wordPatternMatchHelper(pStart + 1, pattern, i + 1,                         str, forwardMap, invertedMap)) {                     return true;                 }                                   forwardMap.remove(pChar);                 invertedMap.remove(curr);             } else if (forwardMap.containsKey(pChar) && invertedMap.containsKey(curr)) {                 String dict = forwardMap.get(pChar);                 char pCharDict = invertedMap.get(curr);                                   // IMPORTANT !! If not equal, instead of returnning false immedidately,                 // We need to try other longer substrings.                 if (!dict.equals(curr) || pCharDict != pChar) {                     continue;                 }                                   if (wordPatternMatchHelper(pStart + 1, pattern, i + 1, str,                         forwardMap, invertedMap)) {                     return true;                 }             }         }                   return false;     } }