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.
递归的来搞。比较粗暴。
class Solution { public: bool isScramble(string s1, string s2) { int n = s1.size(); if (!isSameChar(s1, s2)) return false; if (s1 == s2) return true; for (int i = 1; i < n; i++) { string s11 = s1.substr(0, i); string s12 = s1.substr(i); string s21 = s2.substr(0, i); string s22 = s2.substr(i); if (isScramble(s11, s21) && isScramble(s12, s22)) return true; s21 = s2.substr(0, n - i); s22 = s2.substr(n - i); if (isScramble(s11, s22) && isScramble(s12,s21)) return true; } return false; } bool isSameChar(string a, string b) { int c[256] = {0}; for (int i = 0; i < a.size(); i++) { c[a[i]]++; } for (int i = 0; i < b.size(); i++) { if (--c[b[i]] < 0) return false; } return true; } };
dp[i][j][k] means : s1[i~i+k], s2[j~j+k] is scramble.
// dp[i][j][k] =
// (dp[i][j][t] && dp[i+t][j+t][k-t]) ||
// (dp[i][j+k-t][t] &&dp[i+t][j][k-t]), (1<= t <= k-1)
Note:
loop need to begin from n - 1 to 0, if not, the result is not correct.
because s[0][0][n] need k from 1~n-1, so s[1][1][n-1] must be in the front of s[0][0][n].
class Solution { public: bool isScramble(string s1, string s2) { int n = s1.size(); bool dp[100][100][100] = {0}; memset(dp, 0, sizeof(dp)); // dp[i][j][k] // if true, s1[i~i+k], s2[j~j+k] match. // else dismatch. // dp[i][j][k] = // (dp[i][j][t] && dp[i+t][j+t][k-t]) || // (dp[i][j+k-t][t] &&dp[i+t][j][k-t]), (1<= t <= k-1) for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dp[i][j][0] = true; dp[i][j][1] = (s1[i] == s2[j]); } } for (int i = n - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { for (int k = 2; (i+k <= n) && (j+k <= n); k++) { for (int t = 1; t < k; t++) { if (dp[i][j][k]) break; dp[i][j][k] |= (dp[i][j][t] && dp[i+t][j+t][k-t]) || (dp[i][j+k-t][t] && dp[i+t][j][k-t]); } } } } return dp[0][0][n];; } };
相关推荐
python python_leetcode题解之087_Scramble_String
javascript js_leetcode题解之87-scramble-string.js
c语言基础 c语言_leetcode题解之0087_scramble_string.zip
在LeetCode平台上,字符串(String)专题是编程爱好者和求职者经常练习的重要部分。这个专题涵盖了字符串处理的各种算法问题,旨在提升编程者对字符串操作的熟练度和理解。在这个压缩包中,"LeetCode-String-master"很...
Implement atoi to convert a string to an integer. Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input ...
java java_leetcode题解之Magical String.java
python python_leetcode题解之Binary String With Substrings Representing
c语言入门 c语言_leetcode题解perform-string-shifts.c
java java_leetcode题解之Flip String to Monotone Increasing.java
java java_leetcode题解之Construct String from Binary Tree.java
Reverse words in a string-leetcode
vs code LeetCode 插件
java入门 java_leetcode题解之008_String_to_Integer(atoi)
《Python版LeetCode题解全集详解》 LeetCode是一个广受欢迎的在线编程挑战平台,致力于帮助程序员提升技能,特别是面试准备。这个压缩包“lc-all-solutions-master”包含了使用Python语言解决LeetCode所有问题的...
《使用leetcode-editor在IDE中进行LeetCode练习的全方位指南》 LeetCode是一个广受欢迎的在线编程练习平台,它提供了一系列的算法题目供程序员们提升技能。对于习惯在集成开发环境(IDE)中工作的开发者来说,将...
c语言入门 C语言_leetcode题解之08-string-to-integer-atoi.c
"IDEA leetcode-editor插件"就是将这两者结合的工具,允许用户在IDEA中直接进行LeetCode的编程挑战,无需离开开发环境,提高了刷题的便捷性。 该插件的主要功能包括: 1. **离线模式**:在无法访问LeetCode官网的...
js js_leetcode题解之8-string-to-integer-(atoi).js
Java的String类提供了丰富的API来处理字符串。 2. **链表**: - 链表题目通常涉及节点的插入、删除和遍历。Java中的LinkedList类提供了链表操作的基础,但解题时往往需要自定义节点类。 3. **栈与队列**: - 栈...
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...