What's the time complexity for my accepted java code below?


  • 0

    I include my accepted java code below. It is fairly easy to understand. It uses O(mn) space, but I can't figure out what's the time complexity. Can anyone help?

    public class Solution {
            private Map<String, Boolean> buffer; 
            
            public boolean isInterleave(String s1, String s2, String s3) {
                char[] a,b,c;
                a = s1==null ? new char[0] : s1.toCharArray();
                b = s2==null ? new char[0] : s2.toCharArray();
                c = s3==null ? new char[0] : s3.toCharArray();
                
                if(c.length != a.length + b.length) return false;
                
                buffer = new HashMap<>();
                
                return checkInterleave(a, 0, b, 0, c, 0);
            }
            
            private boolean checkBuffer(char[] s1, int i, char[] s2, int j, char[] s3, int k) {
                 String key = String.format("%d,%d,%d", i, j, k);
                 if(buffer.containsKey(key)) {
                       return buffer.get(key);
                 } else  {
                       boolean result = checkInterleave(s1, i, s2, j, s3, k);
                       buffer.put(key, result);
                       return result;
                 }
            }
            
            private boolean checkInterleave(char[] s1, int i, char[] s2, int j, char[] s3, int k) {
                if(k>=s3.length) return true;
                if(i >= s1.length && j>=s2.length) return false;
                
                if(i >= s1.length) {
                    if(s3[k] != s2[j]) return false;
                    
                    return checkBuffer(s1, i, s2, j+1, s3, k+1); 
                }
                
                if(j >= s2.length) {
                    if(s3[k] != s1[i]) return false;
                    return checkBuffer(s1, i+1, s2, j, s3, k+1);
                }
                
                if(s3[k] != s1[i] && s3[k] != s2[j]) return false;
                
                if(s3[k] == s1[i] && s3[k] == s2[j]) {
                    if(checkBuffer(s1, i, s2, j+1, s3, k+1)) return true;
                    return checkBuffer(s1, i+1, s2, j, s3, k+1);
                }
                
                if(s3[k] == s1[i]) {
                    return  checkBuffer(s1, i+1, s2, j, s3, k+1);
                }else 
                    return  checkBuffer(s1, i, s2, j+1, s3, k+1);
                }
            }
        }

Log in to reply
 

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