LC 91 interleaving string

这一题很有意思  但dfs有一处不是特别懂 直接帖了一个discussion的答案  红字处是标明已经记录的搜索位置  搜索位置用x * width + y来表示一个x-y2D矩阵中 （x,y）的位置
道理都懂 可是这个过不了“aa”, "ab", "aaba"这个test case 但是改成p1 * s3.length() + p2...这就能过了  有点迷 求各位大神指教

···

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;
        HashSet<Integer> cache = new HashSet<Integer>();
        return isInterleave0(s1, s2, s3, 0, 0, cache);
    }

    private boolean isInterleave0(String s1, String s2, String s3, int p1, int p2, HashSet<Integer> cache) {
        if (p1 + p2 == s3.length())
            return true;
        if (cache.contains(p1 * s2.length() + p2))
            return false;
        // no need to store actual result.
        // if we found the path, we have already terminated.
        cache.add(p1 * s2.length() + p2);
        boolean match1 = p1 < s1.length() && s3.charAt(p1 + p2) == s1.charAt(p1);
        boolean match2 = p2 < s2.length() && s3.charAt(p1 + p2) == s2.charAt(p2);
        if (match1 && match2)
            return isInterleave0(s1, s2, s3, p1 + 1, p2, cache) ||
                   isInterleave0(s1, s2, s3, p1, p2 + 1, cache);
        else if (match1)
            return isInterleave0(s1, s2, s3, p1 + 1, p2, cache);
        else if (match2)
            return isInterleave0(s1, s2, s3, p1, p2 + 1, cache);
        else
            return false;
    }
}



补充内容 (2017-3-12 18:55):
已解决  p1 是从0 -> s1.length（） p2 是 0 ---> s2.length()  所以矩阵的长宽度应该是s1.length()+1, s2.length() + 1这样来表示一个坐标在矩阵中的位置  

补充内容 (2017-3-12 18:55):
版主可以删贴了