- 浏览: 141971 次
-
文章分类
- 全部博客 (189)
- Tree (14)
- Dynamic Programming (34)
- Array (20)
- Search (1)
- Hash (12)
- Backtracking (22)
- Divide and Conque (8)
- Greedy (6)
- Stack (12)
- software (0)
- List (7)
- Math (22)
- Two pointers (16)
- String (20)
- Linux (1)
- Sliding Window (4)
- Finite State Machine (1)
- Breadth-first Search (7)
- Graph (4)
- DFS (6)
- BFS (3)
- Sort (9)
- 基础概念 (2)
- 沟通表达 (0)
- Heap (2)
- Binary Search (15)
- 小结 (1)
- Bit Manipulation (8)
- Union Find (4)
- Topological Sort (1)
- PriorityQueue (1)
- Design Pattern (1)
- Design (1)
- Iterator (1)
- Queue (1)
最新评论
-
likesky3:
看了数据结构书得知并不是迭代和递归的区别,yb君的写法的效果是 ...
Leetcode - Graph Valid Tree -
likesky3:
迭代和递归的区别吧~
Leetcode - Graph Valid Tree -
qb_2008:
还有一种find写法:int find(int p) { i ...
Leetcode - Graph Valid Tree -
qb_2008:
要看懂这些技巧的代码确实比较困难。我是这么看懂的:1. 明白这 ...
Leetcode - Single Num II -
qb_2008:
public int singleNumber2(int[] ...
Leetcode - Single Num II
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关系。
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]; }
发表评论
-
Leetcode - Ugly Number II
2015-08-24 22:54 1189[分析] 暴力的办法就是从1开始检查每个数是否是丑数,发现丑数 ... -
Leetcode - Paint House II
2015-08-20 20:37 1630There are a row of n houses, ea ... -
Leetcode - Maximum Square
2015-08-16 13:33 544Given a 2D binary matrix filled ... -
Leetcode - Paint House
2015-08-16 10:48 1172There are a row of n houses, ea ... -
Leetcode - Different Ways to Add Parentheses
2015-07-29 20:21 1233Given a string of numbers and o ... -
Jump Game II
2015-07-05 16:49 577Given an array of non-negative ... -
Leetcode - Jump Game
2015-07-05 15:52 553Given an array of non-negative ... -
Leetcode - Interleaving String
2015-06-07 11:41 636Given s1, s2, s3, find whe ... -
Leetcode - Wildcard Matching
2015-06-06 20:01 1012Implement wildcard pattern ma ... -
Leetcode - Maximal Square
2015-06-04 08:25 641Given a 2D binary matrix fille ... -
Leetcode - Palindrome Partition II
2015-05-21 21:15 702Given a string s, partition ... -
Leetcode - Palindrome Partition
2015-05-21 09:56 808Given a string s, partition s s ... -
Leetcode - House Robber II
2015-05-20 22:34 795Note: This is an extension of ... -
Leetcode - Maximum Rectangle
2015-05-20 08:58 517Given a 2D binary matrix fill ... -
Leetcode - Regular Expression Matching
2015-05-16 16:31 432Implement regular expression ma ... -
Leetcode - Distinct Subsequences
2015-05-01 16:56 542Given a string S and a string T ... -
Leetcode - Best Time to Buy and Sell Stock IV
2015-05-01 16:11 638Say you have an array for which ... -
Leetcode - Best Time to Buy and Sell Stock IV
2015-04-23 09:59 0public class Solution ... -
Leetcode - Best Time to Buy and Sell Stock III
2015-04-23 09:04 506Say you have an array for whi ... -
Leetcode - Dungeon Game
2015-04-21 09:50 491The demons had captured the pr ...
相关推荐
在JavaScript中解决LeetCode题目“Scramble String”的题解主要涉及字符串操作和动态规划的技巧。Scramble String问题是一个典型的字符串变形验证问题,需要判断一个字符串是否可以通过重新排列另一个字符串的所有...
在这个“c语言-leetcode题解之0087-scramble-string.zip”压缩包中,我们可以预见到一个或多个C语言源代码文件,这些文件包含了针对LeetCode平台上编号为87的题目的解决方案。LeetCode是一个提供在线编程题目和面试...
python python_leetcode题解之087_Scramble_String
3. 题目87:扫描线排序 (Scramble String) 这是一个字符串处理问题,通过递归地分割字符串并比较子串的排序来判断是否为原始字符串的乱序版本。解题策略通常包括字符串处理、递归和排序。 4. 题目79:单词搜索 ...