GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — leet-code/Java/Scramble String.java at master · awangdev/leet-code Expand file tree/ Copy pathScramble String.javaMore file actions executable file ·193 lines (162 loc) · 6.64 KB / Copy pathScramble String.javaFile metadata and controlsexecutable file ·193 lines (162 loc) · 6.64 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 H 1518594579 tags: DP, String, Interval DP - 给两个string S, T. 检验他们是不是scramble string. - scramble string 定义: string可以被分拆成binary tree的形式, 也就是切割成substring; - 旋转了不是leaf的node之后, 形成新的substring, 这就是原来string的 scramble. #### Interval DP 区间型 - 降维打击, 分割, 按照长度来dp. - dp[i][j][k]: 数组S从index i 开始, T从index j 开始, 长度为k的子串, 是否为scramble string ##### Break down - 一切两半以后, 看两种情况: , 或者不rotate这两半. 对于这些substring, 各自验证他们是否scramble. - 不rotate分割的两半: S[part1] 对应 T[part1] && S[part2] 对应 T[part2]. - rotate分割的两半: S[part1] 对应 T[part2] && S[part2] 对应 T[part1]. ##### Initialization - len == 1的时候, 其实无法旋转, 也就是看S,T的相对应的index是否字符相等. - initialization非常非常重要. 很神奇, 这个initailization 打好了DP的基础, 后面一蹴而就, 用数学表达式就算出了结果. - input s1, s2 在整个题目的主要内容里面, 几乎没有用到, 只是用在initialization时候. - More details, 看解答 ``` /* 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. */ /* Thoughts: Want to determin the given string S can be scramble/rotate to T. With the tree formation, it leads us to think of the string in partition: can S[i,j] be scambled to T[i,j]? If all substrings can be in scrambled format, it'll return true. dp[i][j][h][k]: can S(i, j) be scrambled to T(h, k)? Reduce it to dp[i][j][k]: starting from index i for S, index j for T, with length k. Can the substrings be scramble? End: want dp[0][0][n] to be srambled. Need size to be boolean dp[n][n][n + 1] with len == 0, always false with len == 1, if S[i]==T[j], then true. with len == 2, do dp; increase length from 1 ~ len, perform dp. Consider two conditions: rotate parent string || not rotating parent string */ class Solution { public boolean isScramble(String s1, String s2) { if (s1 == null || s2 == null) { return s1 == null && s2 == null; } if (s1.length() != s2.length()) { return false; } if (s1.equals(s2)) { return true; } int n = s1.length(); boolean[][][] dp = new boolean[n][n][n + 1]; int len = 1; // Initialize with len = 1; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dp[i][j][1] = s1.charAt(i) == s2.charAt(j); } } // len = 2 for (len = 2; len <= n; len++) { for (int i = 0; i <= n - len; i++) { for (int j = 0; j <= n - len; j++) { for (int w = 1; w < len; w++) { // w = length of 1st substring dp[i][j][len] |= dp[i][j][w] && dp[i + w][j + w][len - w]; // not rotating parent string dp[i][j][len] |= dp[i][j + (len - w)][w] && dp[i + w][j][len - w]; // not rotating parent string } } } } return dp[0][0][n]; } } /* Thoughts: 两个string, 代号 S, T 中间砍一刀, 分开两边. 要么是左右交换, 要么是不交换. 首先有了dp[i][j][k][h]: 分隔开来的S[i, j] 跟 T[k, h]是否是scramble string? want to have dp[0][n][0][n] == true 变成了4维数组. 优化: 4维数组, 但是自由度只有3: 有3个变量可以确定第四个变量: 因为scramble string的长度相等, 所以 j - I = h - k => h = j + k- I 也就是说, 我们可以降维, 不需要4维数组. 降维: 最后一个维度省略, 变成了 length为维度: *** dp[i][j][k]: 数组S从index i 开始, T从index j 开始, 长度为k的子串, 是否为scramble string? 等式需要细心写出来: 分割scramble过后, 原string定为S, 生成的string定为T 分割开来一刀, 分别割成 S1,S2, 和 T1,T2 假设S/T的总长都是k, 而分割点割在了位置为w的地方. 两种情况: 子序列不换位置: 要求分割开来的S1和T1是scramble, S2和T2是scramble S1和T1的关系: dp[i][j][w] => s1 从 index[i] 割 w length, s2从index[j]割了 w length; 是否是scramble string S2和T2的关系: dp[i + w][j + w][k - w] => S2和T2都在割过w length后的地方, 也就是i+w, j+w; 长度是总长减去w: k - w. 子序列换位置:要求分开的s1和s2换位置; 也就是s1对应的t1, 现在跑到了后面的位置 S1和T1的关系: s1在原地, t1换到了后面: t1还是w length, 所以位置变成了 j + (k - w) S2和T2的关系: s2照旧在i+w的位置, t2换到了最前面: index j 综合上面的 情况, 并且让w循环[1, k-1] dp[i][j][k] = OR{dp[i][j][w] && dp[i + w][j + w][k - w]}, where w = [1, k-1] OR OR{dp[i][j + k - w][w] && dp[i + w][j][k - w]}, where w = [1, k-1] */ class Solution { public boolean isScramble(String s1, String s2) { if (s1 == null || s2 == null || s1.length() != s2.length()) { return false; } int n = s1.length(); boolean[][][] dp = new boolean[n][n][n + 1]; // len = 1 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dp[i][j][1] = s1.charAt(i) == s2.charAt(j); } } // len = 2 for (int len = 2; len <= n; len++) { for (int i = 0; i <= n - len; i++) { for (int j = 0; j <= n - len; j++) { // dp[i][j][len] = false; // default is false as well for (int w = 1; w < len; w++) { dp[i][j][len] |= (dp[i][j][w] && dp[i + w][j + w][len - w]); dp[i][j][len] |= (dp[i][j + len - w][w] && dp[i + w][j][len - w]); } } } } return dp[0][0][n]; } } ``` |
| You are visitor 01402503 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |