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.

    public boolean wordPatternMatch(String pattern, String str) {
        if(pattern.length() == 0 || str.length() == 0) 
            return pattern.length() == str.length();

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

        return Helper(str, pattern, pToS, sToP);
    }

    private boolean Helper(String str, String pattern, Map<Character, String> pToS, Map<String, Character> sToP){

        if(str.length() == 0 || pattern.length() == 0) 
            return str.length() == pattern.length();

        boolean flag = false;
        char p = pattern.charAt(0);

        if(pToS.get(p) != null){
            String ms = pToS.get(p);
            Character mp = sToP.get(ms);
            if(str.startsWith(ms) && mp != null && mp == p){
                flag |= Helper(str.substring(ms.length()), pattern.substring(1), pToS, sToP);
            }else return false;
        }
        else{
            for(int i = 0 ; i < str.length(); i++){
                String s = str.substring(0, i + 1);
                if(sToP.get(s) == null){
                    pToS.put(p, s);
                    sToP.put(s, p);

                    flag |= Helper(str.substring(i + 1), pattern.substring(1), pToS, sToP);

                    pToS.remove(p);
                    sToP.remove(s);
                }
            }
        }

        return flag;
    }