AC Java Solution using Dynamic Programming (or Memorial Search)


  • 0
    C

    This is supposed to be an optimization of the simple solutions in the discussion board, because I'm using dynamic programming to store calculated states. But somehow it's actually slower. I guess it is because of the test cases.

    For the DP matrix "scramble", scramble[i][j][k] means the substring of 's1' start at 'i' with length 'k' and the substring of 's2' start at 'j' with length'k' is scramble.

    public boolean isScramble(String s1, String s2) {
            boolean[][][] scramble = new boolean[s1.length() + 1][s1.length() + 1][s1.length() + 1];
            boolean[][][] visited = new boolean[s1.length() + 1][s1.length() + 1][s1.length() + 1];
            for (int i = 0; i < s1.length(); i++) {
                for (int j = 0; j < s2.length(); j++) {
                    scramble[i][j][1] = s1.charAt(i) == s2.charAt(j);
                    visited[i][j][1] = true;
                }
            }
            return isScramble(s1, s2, 0, 0, s1.length(), scramble, visited);
        }
        
        public boolean isScramble(String s1, String s2, int i1, int i2, int len, boolean[][][] scramble, boolean[][][] visited) {
            if (visited[i1][i2][len]) return scramble[i1][i2][len];
            visited[i1][i2][len] = true;
            
            if (s1.equals(s2)) {
                scramble[i1][i2][len] = true;
                return true;
            }
            
            boolean result = false;
            for (int i = 1; i < s1.length(); i++) {
                String s11 = s1.substring(0, i);
                String s12 = s1.substring(i, s1.length());
                String s21 = s2.substring(s1.length() - i, s1.length());
                String s22 = s2.substring(0, s1.length() - i);
                String s23 = s2.substring(0, i);
                String s24 = s2.substring(i, s1.length());
                if ((isScramble(s11, s21, i1, i2 + s1.length() - i, i, scramble, visited) && isScramble(s12, s22, i1 + i, i2, s1.length() - i, scramble, visited)) ||
                    (isScramble(s11, s23, i1, i2, i, scramble, visited) && isScramble(s12, s24, i1 + i, i2 + i, s1.length() - i, scramble, visited))) {
                    scramble[i1][i2][len] = true;
                    return true;
                }
            }
            
            scramble[i1][i2][len] = false;
            return false;
        }
    

  • 0
    M

    Hi I found my DP solution is slower too! I also though it's because of the test case since
    I ran few of the test cases and found only few of the functions get into check DP result.


  • 0
    C
    This post is deleted!

  • 0
    C

    @mancx111 Cool! Glad to hear someone shares similar ideas! Thank you!


Log in to reply
 

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