Java DFS, 5 ms


  • 0
    V
    public class Solution 
    {
        HashMap<String, Boolean> hm;
        boolean isInt;
        public boolean isInterleave(String s1, String s2, String s3) 
        {
            if(s1.length() + s2.length() != s3.length())
                return false;
            isInt = false;
            hm = new HashMap<String, Boolean>();
            return dfs(s1, 0, s2, 0, s3, 0);
            //return isInt;
        }
        boolean dfs(String s1, int i1, String s2, int i2, String s3, int i3)
        {
            if(hm.containsKey(s1.substring(i1) + "|" + s2.substring(i2)))
            {
                boolean cac = hm.get(s1.substring(i1) + "|" + s2.substring(i2));
                if(cac)
                    isInt = true;
                return cac;
            }
            if(i3 == s3.length())
            {
                isInt = true;
                return true;
            }
            boolean retVal = false;
            if(!isInt && i2 < s2.length() && i1 < s1.length() && s1.charAt(i1) == s3.charAt(i3) 
                && s2.charAt(i2) == s3.charAt(i3))
            {
                retVal = dfs(s1, i1 + 1, s2, i2, s3, i3 + 1);
                if(!retVal)
                    retVal = dfs(s1, i1, s2, i2 + 1, s3, i3 + 1);
            }        
            else if(!isInt && i1 < s1.length() && s1.charAt(i1) == s3.charAt(i3))
                retVal = dfs(s1, i1 + 1, s2, i2, s3, i3 + 1);
            else if(!isInt && i2 < s2.length() && s2.charAt(i2) == s3.charAt(i3))
                retVal = dfs(s1, i1, s2, i2 + 1, s3, i3 + 1);
            hm.put(s1.substring(i1) + "|" + s2.substring(i2), retVal);
            return retVal;
        }
    }

Log in to reply
 

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