图片 1Screenshot
from 2016-01-31 21:01:22.png

问题描述

Given two strings s1 and s2 of the same length, determine if s2
is a scrambled string of s1.
问题描述详见LeetCode页面。

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”:

递归的方法

题目:

My code:

问题分析

将s1切割成两部分,将s2也切割成相同长度的两部分(有两种切割方法),判断s2的子串是否为s1的scrambled
string,递归解题。
hint:在递归前先判断一下两个字符串的组成字母是否一致,不一致直接返回False。

 great 
   /  \\ 
  gr eat
 / \\ / \\
g r e at 
      / \\ a t
class Solution:
    # @return a boolean
    def isScramble(self, s1, s2):
        if len(s1)!=len(s2): 
            return False
        if s1==s2: 
            return True
        '''
        l1=list(s1)
        l2=list(s2)
        l1.sort()
        l2.sort()
        if l1!=l2:
            return False
        '''
        zd1={};zd2={}
        for s in s1:
            if s not in zd1:
                zd1[s] = 1
            else:
                zd1[s] += 1
        for s in s2:
            if s not in zd2:
                zd2[s] = 1
            else:
                zd2[s] += 1
        if zd1 != zd2:
            return False
        length=len(s1)
        for i in range(1,length):
            if self.isScramble(s1[:i],s2[:i]) and self.isScramble(s1[i:],s2[i:]): 
                return True
            if self.isScramble(s1[:i],s2[length-i:]) and self.isScramble(s1[i:],s2[:length-i]): 
                return True
        return False

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

public class Solution { public boolean isScramble(String s1, String s2) { if (s1 == null || s2 == null) return false; else if (s1.length() != s2.length return false; else if (!isSame return false; else if (s1.equals return true; /** split string: [0, i), [i, s1.length */ for (int i = 1; i < s1.length { String s11 = s1.substring; String s12 = s1.substring(i, s1.length; String s21 = s2.substring; String s22 = s2.substring(i, s2.length; String s23 = s2.substring(s1.length() - i, s1.length; String s24 = s2.substring(0, s1.length; if (isScramble && isScramble) return true; if (isScramble && isScramble) return true; } return false; } private boolean isSame(String s1, String s2) { char[] c1 = s1.toCharArray(); char[] c2 = s2.toCharArray(); Arrays.sort; Arrays.sort; s1 = new String; s2 = new String; return s1.equals; }}

AC代码

class Solution(object):
    def isScramble(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        if len(s1) != len(s2):
            return False
        n = len(s1)
        if n == 1:
            return s1 == s2
        dic1 = {}
        for c in s1:
            if dic1.has_key(c):
                dic1[c] += 1
            else:
                dic1[c] = 1
        for c in s2:
            if not dic1.has_key(c) or dic1[c] == 0:
                return False
            dic1[c] -= 1
        for i in range(1, n):
            if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]) or self.isScramble(s1[:i], s2[n-i:]) and self.isScramble(s1[i:], s2[:n-i]):
                return True
        return False

Runtime: 56 ms, which beats 100.00% of Python submissions.
(有偶然性但是我不想再交啦23333)

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”

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

这道题目我是没有思路的。看了答案之后才有了思路。这个解法是暴力解法,具体复杂度是多少,我觉得是
2 ^ ns1, s2, 如果从 i 处切开那么就比较,s1[0, i) with s2[0, i) and
s1[i, len) with s2[i, len)
是否为scramble然后这两个子串可以继续递归下去。这是一种情况。第二种情况,s1[0,
i) with s2[len – i, len) and s1[i, len) with s2[0, len – i)
是否为scramble这两种情况只要有一种情况是scramble,就return
true,否则return false然后进一步递归下去。复杂度个人估计,O

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

解法2,Dynamic ProgrammingMy code:

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”.

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

public class Solution { public boolean isScramble(String s1, String s2) { if (s1 == null || s2 == null) return false; else if (s1.length() != s2.length return false; else if (!isSame return false; else if (s1.equals return true; /** using dp * dp[i][j]][k] = 1 means s1.substring and s2.substring is scramble */ int len = s1.length(); int[][][] dp = new int[len][len][len + 1]; /** for single character, if s1 == s2, then dp[i][j][1] = 1 */ for (int i = 0; i < len; i++) { for (int j = 0; j < len; j++) { if (s1.charAt == s2.charAt dp[i][j][1] = 1; } } /** start at i, j with len, split at k, * if dp[i][j][k - i] && dp[k][j + k - i][len - ] is true * Or dp[i][j + len - ][k - i] && dp[k][j][len - ] is true * then dp[i][j][len] is true */ for (int l = 2; l <= len; l++) { for (int i = 0; i <= len - l; i++) { for (int j = 0; j <= len - l; j++) { /** split at offset, i + offset, [i, offset), [i + offset, i + l) */ for (int offset = 1; offset < l; offset++) { if (dp[i][j][offset] == 1 && dp[i + offset][j + offset][l - offset] == 1) dp[i][j][l] = 1; if (dp[i][j + l - offset][offset] == 1 && dp[i + offset][j][l - offset] == 1) dp[i][j][l] = 1; } } } } return dp[0][0][len] == 1; } private boolean isSame(String s1, String s2) { char[] c1 = s1.toCharArray(); char[] c2 = s2.toCharArray(); Arrays.sort; Arrays.sort; s1 = new String; s2 = new String; return s1.equals; }}
  rgtae 
    / \\ 
  rg tae 
  / \\ / \\
  r g ta e 
      / \\
       t a

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

这个解法的思路其实和解法1很类似,但是采用了dp这也是我第一次意识到,dp到底是什么东西。Dp就是一台机器,状态机。你给定,初始状态,一套状态跳转到下一个状态的规则。然后让他运行。固定次数后,出来的结果,或者说,模拟的结果,就是你要的结果。所以,dp的关键是,

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.

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t
  1. dp[][] 的物理意义,也有可能是三维数组
  2. 初始状态
  3. 状态间的转换规则
public class Solution {

    public boolean isScramble(char [] s1, int start1, int end1, char[] s2, int start2, int end2){
        if(end1-start1 != end2-start2)
            return false;

        boolean needPassdown = false;
        int sum1=0, sum2=0;
        for(int i = 0; start1+i<=end1; i++){
            if(s1[start1 + i] != s2[start2 + i]){
                needPassdown = true;
            }
            sum1 ^= s1[start1 + i];
            sum2 ^= s2[start2 + i];
        }
        if(!needPassdown){
            return true;
        }
        if(sum1!=sum2){
            return false;
        }

        for(int i = 0; i<end1-start1; i++){
            if(isScramble(s1, start1, start1+i, s2, start2, start2+i) && isScramble(s1, start1+i+1, end1, s2, start2+i+1, end2))
                return true;
            if(isScramble(s1, start1, start1+i, s2, end2-i, end2) && isScramble(s1, start1+i+1, end1, s2, start2, end2-i-1))
                return true;
        }
        return false;
    }

    public boolean isScramble(String s1, String s2) {
        if(s1 == null || s2 == null)
            return false;

        char [] sc1 = s1.toCharArray();
        char [] sc2 = s2.toCharArray();

        return isScramble(sc1, 0, sc1.length-1, sc2, 0, sc2.length-1);
    }
}

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

dp
的好处是,一旦你找到了这三个,那么,再难的题目,也可以在Np-complete的情况下完成。但是,问题是,首先,很难抽象出dp的物理意义。其次,无论情况多么简单,依然会用最复杂的dp去跑。也就是说,他的运行次数是固定的,不会中途结束或者跳一大段。

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

  1. Longest Palindromic
    Substring
    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

greedy的话,就会根据具体情况具体分析,情况好的时候,会跑的很快,不会是一台规定不变的机器。

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.

Anyway, Good luck, Richardo!

思路:

My code:

递归,isScramble(S1[0, i], S2[0, i]) && isScramble(S1[i, N],
S2[i, N])或者isScramble(S1[0, i], S2[N-i, N]) && isScramble(S1[i,
N], S2[0,
i])。判断时尽早返回,比如长度不一,或者两个字符串内的字符出现的频率不一样。

public class Solution { /** * @param s1 A string * @param s2 Another string * @return whether s2 is a scrambled string of s1 */ private boolean checkScramble(String s1,int start1, String s2, int start2, int k, int [][][]visit) { if(visit[start1][start2][k] == 1) return true; if(visit[start1][start2][k] ==-1) return false; if (s1.length() != s2.length { visit[start1][start2][k] = -1; return false; } if (s1.length() == 0 || s1.equals { visit[start1][start2][k] = 1; return true; } if (!isValid { visit[start1][start2][k] = -1; return false; }// Base Cases for (int i = 1; i < s1.length { String s11 = s1.substring; String s12 = s1.substring(i, s1.length; String s21 = s2.substring; String s22 = s2.substring(i, s2.length; String s23 = s2.substring(0, s2.length; String s24 = s2.substring(s2.length() - i, s2.length; if (checkScramble(s11,start1, s21, start2, i, visit) && checkScramble(s12, start1+i, s22, start2+i,k-i, visit)) { visit[start1][start2][k] = 1; return true; } if (checkScramble(s11,start1, s24, start2+k-i, i, visit) && checkScramble(s12,start1+i, s23,start2, k-i, visit)) { visit[start1][start2][k] = 1; return true; } } visit[start1][start2][k] = -1; return false; } public boolean isScramble(String s1, String s2) { int len = s1.length(); int [][][] visit = new int[len][len][len + 1]; return checkScramble(s1,0,s2,0, len, visit); } private boolean isValid(String s1, String s2) { char[] arr1 = s1.toCharArray(); char[] arr2 = s2.toCharArray(); Arrays.sort; Arrays.sort; if (!(new String.equals(new String { return false; } return true; }}
package recursion;

import java.util.Arrays;

public class ScrambleString {

    public boolean isScramble(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        if (m != n) return false;
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        Arrays.sort(c1);
        Arrays.sort(c2);
        if (!isEqual(c1, c2, m)) return false;
        if (m == 1) return true;
        for (int i = 1; i < m; ++i) {
            if (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i, m), s2.substring(i, m))) return true;
            if (isScramble(s1.substring(0, i), s2.substring(m - i, m)) && isScramble(s1.substring(i, m), s2.substring(0, m - i))) return true;
        }
        return false;
    }

    private boolean isEqual(char[] c1, char[] c2, int n) {
        for (int i = 0; i < n; ++i) {
            if (c1[i] != c2[i]) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        ScrambleString s = new ScrambleString();
        System.out.println(s.isScramble("rgtae", "great"));
    }

}

reference:

 

算是 recursive DP + cache, 复杂度还是在 O
左右。这道题目,加不加cache,最终的效果也差不多。

参考链接里,所谓的记忆化搜索,也不过是加了一层cache,并没有彻底地改为:
iteration DP

但是上面的第二种解法,正是iteration DP,三维的DP

说到底,这道题目还是算是 divide and conquer的一种变形。

Anyway, Good luck, Richardo! — 08/24/2016

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图