Word Pattern II -- Leetcode

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-emptysubstring 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.

Answer:

Method: Recursive + Backtrack!

public class Solution {

    public boolean wordPatternMatch(String pattern, String str) {

        Map<Character, String> hmap = new HashMap<Character, String>();

        Set<String> set = new HashSet<String>();

        return Util(pattern, str, 0, 0, hmap, set);

    }

    

    public boolean Util(String pattern, String str, int startP, int startS, Map<Character, String> hmap, Set<String> set){

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

            return true;

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

            return false;

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

            return false;

        }

        

        char pChar = pattern.charAt(startP);

        //case 1

        if(hmap.containsKey(pChar)){

            String tmp = hmap.get(pChar);

            if(startS + tmp.length() - 1 < str.length()){

                String curr = str.substring(startS, startS + tmp.length());

                if(curr.equals(tmp)){

                    return Util(pattern, str, startP+1, startS + tmp.length(), hmap, set);

                }else{

                    return false;

                }

            }else{

                return false;

            }

        }

        

        //case 2

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

            String tmp = str.substring(startS, i+1);

            if(!set.contains(tmp)){

                hmap.put(pChar, tmp);

                set.add(tmp);

                if(Util(pattern, str, startP+1, i+1, hmap, set)){

                    return true;

                }

                hmap.remove(pChar);

                set.remove(tmp);

            }

        }

        return false;

    }

}