I think it's easy to understand


  • 0
    N
    public class Solution {
        public boolean isInterleave(String s1, String s2, String s3) {
            if(s1 == null || s2 == null || s3 == null) return false;
    		if(s1.length() + s2.length() != s3.length()) return false;
    		Node root = new Node(0,0,0);
    		Set<Node> cur = new HashSet<>(Arrays.asList(root));
    		int i = 0;
    		for(;i<s3.length();i++){
    			Set<Node> temp = new HashSet<>();
    			for(Node n:cur){
    				temp.addAll(n.grow(s1, s2, s3));
    			}
    			cur = temp;
    			if(cur.size() == 0) return false;
    			
    		}
    		
            return true;
        }
    }
    
    class Node{
    	int i = -1;
    	int j = -1;
    	int k = -1;
    	
    	Node(int i,int j,int k){
    		this.i = i;
    		this.j = j;
    		this.k = k;
    		//System.out.println(this);
    	}
    	
    	List<Node> grow(String s1,String s2,String s3){
    		
    		List<Node> list = new ArrayList<>();
    		
    		if(i < s1.length() && s3.charAt(k) == s1.charAt(i)){
    			list.add(new Node(i+1,j,k+1));
    		}
    		if(j<s2.length() && s3.charAt(k) == s2.charAt(j)){
    			list.add(new Node(i,j+1,k+1));
    		}
    		return list;
    	}
    	
    	@Override
    	public int hashCode(){
    		Integer value = new Integer(i + j*10 + k*100);
    		return value.hashCode();
    	}
    	
    	@Override
    	public boolean equals(Object obj){
    		if(obj == null) return false;
    		if(!(obj instanceof Node)){
    			return false;
    		}
    		Node n = (Node)obj;
    		if(this.i != n.i || this.j != n.j || this.k != n.k) return false;
    		return true;
    		
    	}
    }
    

Log in to reply
 

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