4ms recursive java


  • 6
    B
    public class Solution {
        Set<String> mem = new HashSet<String>();
        public boolean isInterleave(String s1, String s2, String s3) {
            if(s1.length() == 0 && s2.length() == 0 && s3.length() == 0)
                return true;
            if(mem.contains(s1+"#"+s2)) 
                return false;
            if(s3.length() > 0){
                if(s1.length() > 0 &&  s1.charAt(0) == s3.charAt(0))
                    if(isInterleave(s1.substring(1),s2,s3.substring(1))) return true;
                if(s2.length() > 0 && s2.charAt(0) == s3.charAt(0))
                    if(isInterleave(s1,s2.substring(1),s3.substring(1))) return true;
            }
            mem.add(s1+"#"+s2);
            return false;
        }
    }

  • 0
    H

    What is the time complexity of this algorithm?>=


  • 0
    B

    Without the memoization, the runtime is O(2^(m+n)), where m and n are lengths of s1 and s2 respectively. With memoization, I believe it is O(m.n) because there are m*n possible substrings of s1 and s2. Therefore the function isInterleave can only be executed for a maximum of m*n times. To see why there are only m*n substrings, I have replaced the lines "mem.contains(s1+s3+s2)" and "mem.add(s1+s3+s2);" to mem.contains(s1+"#"+s2) and "mem.add(s1+"#"+s2);" respectively.


  • 0
    S

    @band said in 4ms recursive java:

        if(mem.contains(s1+"#"+s2)) 
    

    Nice solution! I used to use DP way to address it. But I'd like to try different ways.
    Here I don`t understand this: s1+"#"+s2. What does it mean? Could you explain it? Thank you.


  • 0
    B

    @sshen8734
    I am just memorizing that the string 's1 + "#" + s2' is not a valid interleaving of s3. The reason I am having a "#" is to separate the cases 1) "s1 = aa" and "s2 = a" and 2) "s1=a" and "s2=aa". But it may not be necessary.


Log in to reply
 

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