My Java Solution, maybe BFS?


  • 0
    J
        class Pair {
    	int x;
    	int y;
    	public Pair(int x, int y) {
    		this.x = x;
    		this.y = y;
    	}
    	@Override
    	public boolean equals(Object other) {
    		boolean ret = false;
    	    if (other instanceof Pair) {
    	    	Pair that = (Pair) other;
    	    	if (that.x == this.x && that.y == this.y)
    	    		ret = true;
    	    }
    		return ret;
    	}
    	@Override
    	public int hashCode() {
    		return this.x+this.y;
    	}
    }
    public class Solution {
        public boolean isInterleave(String s1, String s2, String s3) {
            if (s1 == null || s1.length() == 0) {
                return s2.equals(s3);
            }
            if (s2 == null || s2.length() == 0) {
                return s1.equals(s3);
            }
            if (s1.length() + s2.length() != s3.length())
                return false;
            int count = 0;  
            HashSet<Pair> pre = new HashSet<Pair>();
            HashSet<Pair> cur = new HashSet<Pair>();
            pre.add(new Pair(0, 0));
            for (int i = 0; i < s3.length(); i++) {
                if(pre.isEmpty()) return false;
                for (Pair p : pre) {
                    if (p.x < s1.length() && s1.charAt(p.x) == s3.charAt(i)) {
                        cur.add(new Pair(p.x+1, p.y));
                    }
                    if (p.y < s2.length() && s2.charAt(p.y) == s3.charAt(i)) {
                    	cur.add(new Pair(p.x, p.y+1));
                    }
                }
                pre = cur;
                cur = new HashSet<Pair>();
            }
            return true;
        }
    }

Log in to reply
 

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