diff options
author | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
commit | 7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch) | |
tree | eb7a24ee2067f92245c57bb118e85a1baf15df50 /other/scramble_string.cpp | |
parent | 5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff) | |
download | leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip |
chore: move cpp and rust code to directory
Diffstat (limited to 'other/scramble_string.cpp')
-rw-r--r-- | other/scramble_string.cpp | 55 |
1 files changed, 55 insertions, 0 deletions
diff --git a/other/scramble_string.cpp b/other/scramble_string.cpp new file mode 100644 index 0000000..da6b92d --- /dev/null +++ b/other/scramble_string.cpp @@ -0,0 +1,55 @@ +// 87. Scramble String +#include "leetcode.h" + +/* + * string 's' can be scrambled to get string 't' using the following algorithm: + * if length of string is 1, exit + * if lenght of string is > 1: + * split string into two non-empty substrings at random index + * randomly decide to swap two substrings or to keep them in same order + * apply step 1 recursively + * given two strings 's1' and 's2' of the same length, return true if 's2' is a + * scrambled string of 's1', otherwise return false + */ + +class Solution { +public: + bool isScramble(string s1, string s2) { + if (s1.size() != s2.size()) + return false; + return is_scrambled(s1, s2); + } + +private: + unordered_map<string, bool> um; + bool is_scrambled(string s1, string s2) { + int n = s1.size(); + if (s1 == s2 || n == 0) + return true; + string key = s1 + ' ' + s2; + if (um.find(key) != um.end()) + return um[key]; + bool flag = false; + for (int i = 1; i < n; i++) { + if (is_scrambled(s1.substr(0, i), s2.substr(n - i, i)) && + is_scrambled(s1.substr(i, n - i), s2.substr(0, n - i))) { + flag |= true; + break; + } + if (is_scrambled(s1.substr(0, i), s2.substr(0, i)) && + is_scrambled(s1.substr(i, n - i), s2.substr(i, n - i))) { + flag |= true; + break; + } + } + um[key] = flag; + return flag; + } +}; + +int main() { + Solution obj; + printf("%d\n", obj.isScramble("great", "rgeat")); // expect: 1 + printf("%d\n", obj.isScramble("abcde", "caebd")); // expect: 0 + printf("%d\n", obj.isScramble("a", "a")); // expect: 1 +} |