`

Leetcode - Scramble String

 
阅读更多
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
/ \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
/ \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
/ \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

[balabala] 暴力解决枚举出s1的全部scramble string, 存在大量重复计算;分段比较s1,s2也存在大量重复计算,比如s1=abcdef, s2=dcabef, isScramble(bcdef, cabef) 就会重复计算isScramble(cdef, abef)。使用动态规划,保存s1, s2每个位置处各种长度对应的字串的匹配情况,dp[l][i][j]表示s1[i, i+l) 和 s2[j, j+l)是否是scramble关系。

// timeout
public boolean isScramble1(String s1, String s2) {
        if (s1 == null || s2 == null || s1.length() != s2.length())
            return false;
        if (s1.equals(s2))
            return true;
        int lengthS1 = s1.length();
        for (int i = 1; i < lengthS1; i++) {
            boolean cond1 = isScramble(s1.substring(0, i), s2.substring(0, i)) 
                    && isScramble(s1.substring(i, lengthS1), s2.substring(i, lengthS1));
            boolean cond2 = isScramble(s1.substring(0, i), s2.substring(lengthS1 - i, lengthS1)) 
                    && isScramble(s1.substring(i, lengthS1), s2.substring(0, lengthS1 - i));
            if (cond1 || cond2)
                return true;
        }
        return false;
    }
    
    public boolean isScramble(String s1, String s2) {
        if (s1 == null || s2 == null || s1.length() != s2.length())
            return false;
        if (s1.equals(s2))
            return true;
        int length = s1.length();
        boolean[][][] dp = new boolean[length + 1][length][length];
        for (int l = 1; l <= length; l++) {
            for (int i = 0; i <= length - l; i++) {
                for (int j = 0; j <= length - l; j++) {
                    if (l == 1) {
                        dp[1][i][j] = s1.charAt(i) == s2.charAt(j);
                    } else {
                        for (int k = 1; k < l; k++) {
                            dp[l][i][j] = (dp[k][i][j] && dp[l - k][i + k][j + k])
                                            || (dp[k][i][j + l - k] && dp[l - k][i + k][j]);
                            if (dp[l][i][j])
                                break;
                        }
                    }
                }
            }
        }
        return dp[length][0][0];
}



分享到:
评论

相关推荐

    js-leetcode题解之87-scramble-string.js

    在JavaScript中解决LeetCode题目“Scramble String”的题解主要涉及字符串操作和动态规划的技巧。Scramble String问题是一个典型的字符串变形验证问题,需要判断一个字符串是否可以通过重新排列另一个字符串的所有...

    c语言-leetcode题解之0087-scramble-string.zip

    在这个“c语言-leetcode题解之0087-scramble-string.zip”压缩包中,我们可以预见到一个或多个C语言源代码文件,这些文件包含了针对LeetCode平台上编号为87的题目的解决方案。LeetCode是一个提供在线编程题目和面试...

    python-leetcode题解之087-Scramble-String

    python python_leetcode题解之087_Scramble_String

    leetcode1-200题源码(c++)

    3. 题目87:扫描线排序 (Scramble String) 这是一个字符串处理问题,通过递归地分割字符串并比较子串的排序来判断是否为原始字符串的乱序版本。解题策略通常包括字符串处理、递归和排序。 4. 题目79:单词搜索 ...

Global site tag (gtag.js) - Google Analytics