leetcode/src/Scramble_String.cpp at master · zyx4843/leetcode · GitHub

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
// Source : https://oj.leetcode.com/problems/scramble-string/
// Author : zheng yi xiong
// Date   : 2015-01-06

/**********************************************************************************
*
* 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.
*
**********************************************************************************/
#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
	bool isScramble(string s1, string s2) {
		if (s1.size() != s2.size())
		{
			return false;
		}

		if (s1.empty())
		{
			return false;
		}

		int len = s1.size();
		vector<vector<vector<bool>>> bScramble(len + 1, vector<vector<bool>>(len, vector<bool>(len, false)));
		for (int i = 0; i < len; ++i)
		{
			for (int j = 0; j < len; ++j)
			{
				if (s1[i] == s2[j])
				{
					bScramble[1][i][j] = true;
				}
			}
		}

		for (int n = 2; n <= len; ++n)
		{
			for (int i = 0; i + n <= len; ++i)
			{
				for (int j = 0; j + n <= len; ++j)
				{
					for (int k = 1; k < n; ++k)
					{
						if ( (bScramble[k][i][j] && bScramble[n - k][i + k][j + k]) || (bScramble[k][i][j + n - k] && bScramble[n - k][i + k][j]) )
						{
							bScramble[n][i][j] = true;
							break;
						}
					}
				}
			}
		}

		return bScramble[len][0][0];
	}
};

int _tmain(int argc, _TCHAR* argv[])
{
	string s1 = "abcd";
	string s2 = /*"dbca";*/"bdac";
	Solution so;
	bool bScramble = so.isScramble(s1, s2);
	return 0;
}