Backtracking and memoization: O(2^N) worst case runtime


  • 0
    G

    This problem seems to be very tricky, but in fact we can solve it with a pretty usual backtracking algorithm. There are two easy cases to consider and one complicated case:

    1. Case 1: s1[i] is equal to the current character in s3, so we just move i and pos of s3 forward by one.
    2. Case 2: s2[j] is equal to the current character in s3. Do the same as above, but with j
    3. Case 3: s1[i] and s2[j] are equal to the current character in s3. At this point, we do not know which pointer will be the correct one to move. We just try to move pointer i and see what happens. If we are lucky, we will get a valid result. Otherwise we backtrack to this position and move pointer j forward by one.

    The above algorithm takes O(2^N) runtime worst case. We can improve this by using memoization. We create a hashmap which stores indexes of the pointers to positions of s3. Whenever we find a constellation that is invalid, we store it in this map.

    public boolean isInterleave(String s1, String s2, String s3) {
            if (s1 == null || s2 == null || s3 == null || s3.length() != s1.length() + s2.length()) {
                return false;
            }
            
            Map<Integer, List<Integer>> memo = new HashMap<>();
            return interleave(s1, s2, s3, 0, 0, 0, memo);
        }
        
        private boolean interleave(String s1, String s2, String s3, int pos, int i, int j, Map<Integer, List<Integer>> memo) {
            if (pos == s3.length()) {
                return true;
            } else if (memo.containsKey(pos)) {
                List<Integer> indexes = memo.get(pos);
                if (indexes.get(0) == i && indexes.get(1) == j) {
                    return false;
                }
            }
            
            char s3Char = s3.charAt(pos);
            boolean interleaves = false;
            
            if (i < s1.length() && s1.charAt(i) == s3Char) {
                interleaves |= interleave(s1, s2, s3, pos + 1, i + 1, j, memo);
            }
            
            if (interleaves) {
                return true;
            }
            
            if (j < s2.length() && s2.charAt(j) == s3Char) {
                interleaves |= interleave(s1, s2, s3, pos + 1, i, j + 1, memo);
            }
            
            if (!interleaves) {
                List<Integer> indexes = new ArrayList<>();
                indexes.add(i);
                indexes.add(j);
                memo.put(pos, indexes);
            }
            
            return interleaves;
        }
    

Log in to reply
 

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