Share my Java backtracking solution


  • 99

    We can solve this problem using backtracking, we just have to keep trying to use a character in the pattern to match different length of substrings in the input string, keep trying till we go through the input string and the pattern.

    For example, input string is "redblueredblue", and the pattern is "abab", first let's use 'a' to match "r", 'b' to match "e", then we find that 'a' does not match "d", so we do backtracking, use 'b' to match "ed", so on and so forth ...

    When we do the recursion, if the pattern character exists in the hash map already, we just have to see if we can use it to match the same length of the string. For example, let's say we have the following map:

    'a': "red"

    'b': "blue"

    now when we see 'a' again, we know that it should match "red", the length is 3, then let's see if str[i ... i+3] matches 'a', where i is the current index of the input string. Thanks to StefanPochmann's suggestion, in Java we can elegantly use str.startsWith(s, i) to do the check.

    Also thanks to i-tikhonov's suggestion, we can use a hash set to avoid duplicate matches, if character a matches string "red", then character b cannot be used to match "red". In my opinion though, we can say apple (pattern 'a') is "fruit", orange (pattern 'o') is "fruit", so they can match the same string, anyhow, I guess it really depends on how the problem states.

    The following code should pass OJ now, if we don't need to worry about the duplicate matches, just remove the code that associates with the hash set.

    public class Solution {
      
      public boolean wordPatternMatch(String pattern, String str) {
        Map<Character, String> map = new HashMap<>();
        Set<String> set = new HashSet<>();
        
        return isMatch(str, 0, pattern, 0, map, set);
      }
      
      boolean isMatch(String str, int i, String pat, int j, Map<Character, String> map, Set<String> set) {
        // base case
        if (i == str.length() && j == pat.length()) return true;
        if (i == str.length() || j == pat.length()) return false;
        
        // get current pattern character
        char c = pat.charAt(j);
        
        // if the pattern character exists
        if (map.containsKey(c)) {
          String s = map.get(c);
          
          // then check if we can use it to match str[i...i+s.length()]
          if (!str.startsWith(s, i)) {
            return false;
          }
          
          // if it can match, great, continue to match the rest
          return isMatch(str, i + s.length(), pat, j + 1, map, set);
        }
        
        // pattern character does not exist in the map
        for (int k = i; k < str.length(); k++) {
          String p = str.substring(i, k + 1);
    
          if (set.contains(p)) {
            continue;
          }
    
          // create or update it
          map.put(c, p);
          set.add(p);
          
          // continue to match the rest
          if (isMatch(str, k + 1, pat, j + 1, map, set)) {
            return true;
          }
    
          // backtracking
          map.remove(c);
          set.remove(p);
        }
        
        // we've tried our best but still no luck
        return false;
      }
      
    }
    

  • 4
    I

    In your solution similar characters can be matched to the same substring. It's not a bijection.
    For example, wordPatternMatch("ab", "aa") will return true. But it should return false.

    One should check if str.substring(i, k + 1) exists in the map values. So, I would prefer to have another storage (probably, HashSet) containing matched words.


  • 0

    I have just added your test case, thanks.


  • 0

    I have just amended my code to pass the new test case, thanks!


  • 3

    How about str.startsWith(s, i)?


  • 0

    Amazing! That makes the code even cleaner. Thanks Stefan!!


  • 6

    Hi admin, could you also add the following test case to the test suite please?

    wordPatternMatch("aba", "aaaa"), true

    'a' => "a"

    'b' => "aa"

    My original solution (after adding the hash set) should fail in this test case, but actually it got passed in OJ.

    I have fixed the logic of doing the backtracking in my solution, now it makes more sense.


  • 7

    Hi, jeantimex. Great thanks for your sharing :-)

    I try to rewrite it in C++. And, I really hope that C++ string can have a nice Java startsWith :-)

    class Solution {
    public:
        bool wordPatternMatch(string pattern, string str) {
            unordered_set<string> st;
            unordered_map<char, string> mp;
            return match(str, 0, pattern, 0, st, mp);
        }
    private:
        bool match(string& str, int i, string& pat, int j, unordered_set<string>& st, unordered_map<char, string>& mp) {
            int m = str.length(), n = pat.length();
            if (i == m && j == n) return true;
            if (i == m || j == n) return false;
            char c = pat[j];
            if (mp.find(c) != mp.end()) {
                string s = mp[c];
                int l = s.length();
                if (s != str.substr(i, l)) return false;
                return match(str, i + l, pat, j + 1, st, mp);
            } 
            for (int k = i; k < m; k++) {
                string s = str.substr(i, k - i + 1);
                if (st.find(s) != st.end()) continue;
                st.insert(s);
                mp[c] = s;
                if (match(str, k + 1, pat, j + 1, st, mp)) return true;
                st.erase(s);
                mp.erase(c);
            }
            return false;
        }
    };

  • 2

    Thank you very much jianchao! The only thing I don't like in Java is that we need to use .equals() to compare strings, sometimes I forgot that and took me a lot of time to debug :)


  • 0

    Thanks, I have just published your test case.


  • 0
    A

    Thanks for sharing! Your solution is always smart!


  • 0
    C

    can we check map.containsValue(p) instead of using another hashset?
    public class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
    HashMap<String,String> map=new HashMap<String,String>();
    return find(map,pattern,0,str,0);
    }

    public boolean find(HashMap<String,String> map,String pattern,int i,String str,int j)
    {
        if(i==pattern.length()&&j==str.length())
        return true;
        if(i==pattern.length()||j==str.length())
        return false;
        
        String c=pattern.substring(i,i+1);
        if(map.containsKey(c))
        {
            String tem=map.get(c);
            
            if(j+tem.length()>str.length()||!tem.equals(str.substring(j,j+tem.length())))
            return false;
            
            return find(map,pattern,i+1,str,j+tem.length());
        }
        else
        {
            for(int k=j;k<str.length();k++)
            {
                String next=str.substring(j,k+1);
                
                if(map.containsValue(next))  // if c has not been add in map,but next has been added before, which means there are some other character mapping to the next;
                continue;
                
                map.put(c,next);
                
                if(find(map,pattern,i+1,str,k+1))
                return true;
                
                map.remove(c);
            }
        }
        return false;
    }
    

    }


  • 0
    I

    caffery24, sure, it is possible to use containsKey() method. But it is slower, since the method's complexity is O(n).


  • 0
    C

    The problem asks for a bijection between a letter in the pattern and a non-empty substring in the string. So we must use a hashset to avoid duplicate mapping.


  • 0
    O

    same idea with a pruning. 10ms 80%

    public class Solution {
        public boolean wordPatternMatch(String pattern, String s) {
            HashMap<Character, String> h = new HashMap();
            HashSet<String> mapped = new HashSet();
            char[] p = pattern.toCharArray();
            return dfs(0, 0, p, s, h, mapped);
        }
        
        private boolean dfs(int pi, int si, char[] p, String s, HashMap<Character, String> h, HashSet<String> mapped) {
            if (pi == p.length)
                return si == s.length();
                
            for (int needL = 0, restL = s.length() - si, i = pi; i < p.length; i++) {
                needL += h.containsKey(p[i]) ? h.get(p[i]).length() : 1;
                if (needL > restL) return false;    //pruning based on remaining length
            }
            
            if (h.containsKey(p[pi])) {
                String t = h.get(p[pi]);
                return t.length() <= s.length() - si && t.equals(s.substring(si, si + t.length())) 
                    && dfs(pi + 1, t.length() + si, p, s, h, mapped);
            }
            
            for (int i = si; i < s.length(); i++) {
                String t = s.substring(si, i + 1);
                if (mapped.contains(t)) continue;
                h.put(p[pi], t); mapped.add(t);
                if (dfs(pi + 1, i + 1, p, s, h, mapped)) return true;
                h.remove(p[pi]); mapped.remove(t);
            }
            return false;
        }
    }

  • 0
    S

    I have an easy understanding version which beat 100.00% java submits.
    very hard to format my code here. sigh


  • 0
    G

    another minor optimization is change k < str.length() to k <= str.length() - (pat.length() - j).


  • 1
    H

    @caffery24 - What would be the complexity of this code?


  • 0
    P
    This post is deleted!

  • 0
    M

    Regarding the time complexity, I think the worst case is, O(2^n), right?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.