Java DFS with memoization


  • 0
    V

    Memoization here is for failure cases, once any success cases is encountered we stop. If we encounter failure cases, we just skip and try for the next combination, till end of string.

    public class Solution 
    {
        HashSet<String> hs;
        public boolean isMatch(String s, String p) 
        {
            hs = new HashSet<String>();
            return dfs(s, p, 0, 0);
        }
        boolean dfs(String s, String p, int sind, int pind)
        {
            if(hs.contains(p))
                return false;
            hs.add(p);
            if(sind == s.length() && pind == p.length())
                return true;
            int ind = pind;
            while(sind < s.length())
            {
                if(pind + 1 < p.length() && p.charAt(pind + 1) == '*')
                    break;
                if(pind == p.length() || p.charAt(pind) != '.' && p.charAt(pind) != s.charAt(sind))
                    return false;
                sind++;
                pind++;
            }
            if(sind == s.length() && pind == p.length())
                return true;
            if(pind == p.length())
                return false;
            char t = p.charAt(pind);
            int i = 0;
            if(pind + 1 == p.length())
                return false;
            if(p.charAt(pind + 1) != '*')
                return false;
            String prevStr = p.substring(0, pind);
            String nextStr = p.substring(pind + 2, p.length());
            String currStr = "";
            do
            {
                if(dfs(s, prevStr + currStr + nextStr, sind + i, prevStr.length() + i))
                    return true;
                currStr += t;
                if(sind + i == s.length() || currStr.charAt(i) != '.' && currStr.charAt(i) != s.charAt(sind + i))
                    break;
                i++;
                
            }while(true);
            return false;
        }
    }

Log in to reply
 

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