Is There a Better Data Structure? Please Help.


  • 0
    L

    The code is accepted but I have questions about the data structure.
    Please read the comments for details.

    public class Solution {
    
    // this is the data structure I am currently using.
    HashMap<String,Boolean> map = new HashMap<String,Boolean>();
    
    public boolean isInterleave(String s1, String s2, String s3) {
        
        if (s3.length() != s1.length() + s2.length()) return false;
        
        return check(s1,0,s2,0,s3,0);
        
    }
    
    public boolean check(String s1, int i1, String s2, int i2, String s3, int i3){
         
        if (i1 == s1.length()){
            return s3.substring(i3).equals(s2.substring(i2));
        }
        
        if (i2 == s2.length()){
            return s3.substring(i3).equals(s1.substring(i1));
        }
        
        String s = i1 +", " + i2;
        if (map.containsKey(s)){
            
            /** ****************************************************************************************************
             * 
             * Here is my question:
             * 
             * map.get(s) always returns false, because if we find some results that is true, then the whole function
             * returns true, and the HashMap will never be queried again, therefore return map.get(s) or return false 
             * makes no difference;
             * 
             * So, HashMap is used only because we wanted to hash the key, and the space for value is wasted.
             * 
             * Is there any other Data Structure we can use for non-duplicated hash-access, but only stores the key?
             * 
             * *****************************************************************************************************
             */
            // return map.get(s);
            return false;
        }
        
        char c = s3.charAt(i3);
        boolean result = false;
        
        if (c == s1.charAt(i1) && c == s2.charAt(i2) ){
            result = check(s1, i1+1, s2, i2, s3, i3+1) || check(s1, i1, s2, i2+1, s3, i3+1);
        } else if (c==s1.charAt(i1)){
            result = check(s1, i1+1, s2, i2, s3, i3+1);
        } else if (c==s2.charAt(i2)){
            result = check(s1, i1, s2, i2+1, s3, i3+1);
        }
        
        map.put(s,result);
        
        return result;
        }
    }
    
    

Log in to reply
 

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