DFS + memorization


  • 0
    S
    class Solution {
        class Tuple {
            int i;
            int j;
            int k;
            Tuple(int i, int j, int k){
                this.i = i;            
                this.j = j;
                this.k = k;
            }
            @Override
            public boolean equals(Object obj) {
                if (obj == this) {
                    return true;
                }
                if (! (obj instanceof Tuple)) {
                    return false;
                }
                Tuple cmp = (Tuple) obj;
                return this.i == cmp.i && this.j == cmp.j && this.k == cmp.k;
            }
            
            @Override
            public int hashCode() {
                int r = 17;
                r += 31 * r + i;
                r += 31 * r + j;
                r += 31 * r + k;
                return r;
            }
            
        }
        public boolean isInterleave(String s1, String s2, String s3) {
            Set <Tuple> s = new HashSet<>();
            return (helper(s, s1.toCharArray(), 0, s2.toCharArray(), 0, s3.toCharArray(), 0));                            
        }
        
        private boolean helper(Set s, char[] s1, int i, char[] s2, int j, char[] s3, int k) {
            if (i == s1.length && j == s2.length && k== s3.length) return true;
            if (s.contains(new Tuple(i, j, k))) return false;
            if (i < s1.length && k < s3.length && s1[i] == s3[k]) {
                
                if (helper(s, s1, i+1, s2, j, s3, k+1)) {
                    return true;
                }
                else {
                    s.add(new Tuple(i, j, k));
                }
            }
            if (j < s2.length && k < s3.length && s2[j] == s3[k]) {            
                
                if (helper(s, s1, i, s2, j + 1, s3, k+1)) {
                    return true;
                }
                else {
                    s.add(new Tuple(i, j, k));
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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