问题描述
- 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.
public class Solution { /** * @param s1 A string * @param s2 Another string * @return whether s2 is a scrambled string of s1 */ public boolean isScramble(String s1 String s2) { // Write your code here int n = s1.length(); if (s2.length() != n) return false; boolean dp[][][] = new boolean[n][n][n]; // case: length is 1 for (int i=0; i<n; i++) for (int j=0; j<n; j++) dp[i][j][0] = s1.charAt(i) == s2.charAt(j); // case: length is 2....n for (int l=1; l<n; l++) { for (int i=0; i+l<n; i++) { for (int j=0; j+l<n; j++) { for (int k=0; k<l; k++) { if ((dp[i][j][k] && dp[i+k+1][j+k+1][l-1-k]) || (dp[i][j+l-k][k] && dp[i+k+1][j][l-1-k])) dp[i][j][l] = true; } } } } return dp[0][0][n-1]; }}我想问的是 为什么要初始dp[i][j][0]，这样做的意义何在？还有很多动态规划的题目 例如 方格步数 爬楼梯 都要一开始初始化 这样的意义是什么？
解决方案
LeetCode: Scramble String
[LeetCode]Scramble String
[LeetCode]Scramble String