O(n) solution in Java (forward and backward comparison)


#1
public class Solution {
    public int isInterleave(String A, String B, String C) {
        if ((A.length() + B.length()) != C.length()) {
            return 0;
        }
        
        int a1 = 0;
        int a2 = 0;
        int b1 = 0;
        int b2 = 0;
        
        for(int i = 0; i < C.length(); i++) {
            boolean first = true;
            boolean second = true;
            
            if (a1 < A.length() && A.charAt(a1) == C.charAt(i)) {
                a1++;
            } else if (b1 < B.length() && B.charAt(b1) == C.charAt(i)) {
                b1++;
            } else {
                first = false;
            }
            
            if (b2 < B.length() && B.charAt(b2) == C.charAt(i)) {
                b2++;
            } else if (a2 < A.length() && A.charAt(a2) == C.charAt(i)) {
                a2++;
            } else {
                second = false;
            }
            
            if (!first && !second) {
                return 0;
            }
            if (first && !second) {
                a2 = a1;
                b2 = b1;
            } else if (second && !first) {
                a1 = a2;
                b1 = b2;
            }
        }
        return 1;
    }
}