Clear Code, Java 1ms Solution


  • 2
    L
    public class Solution {
        public boolean isInterleave(String a, String b, String c) {
            if (a.length() + b.length() != c.length())
                return false;
            return isInterleave(0, 0, new boolean[a.length() + 1][b.length() + 1], a, b, c);
        }
        public boolean isInterleave(int i, int j, boolean[][] f, String a, String b, String c) {
            if (f[i][j])
                return false;
            else
                f[i][j] = true;
            if (i == a.length() && j == b.length())
                return true;
            if (i < a.length() && a.charAt(i) == c.charAt(i + j) && isInterleave(i + 1, j, f, a, b, c))
                return true;
            if (j < b.length() && b.charAt(j) == c.charAt(i + j) && isInterleave(i, j + 1, f, a, b, c))
                return true;
            return false;
        }
    }
    

    The idea is very clear so that I don't think any explanation is needed. QAQ


Log in to reply
 

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