首页 > 代码库 > LeetCode "Scramble String"
LeetCode "Scramble String"
I have to admit that I‘m still an algorithm rookie: in front of a problem, I got lost on what the nature of the problem is.. usually I made everything too complex unnecessarily.
As the graph on the page shows, it is recursive model. So DFS with pruning is a good choice: http://zhaohongze.com/wordpress/2013/12/12/leetcode-scramble-string/
My code:
class Solution {public: bool hasSameLetters(string s1, string s2) { std::sort(s1.begin(), s1.end()); std::sort(s2.begin(), s2.end()); return s1.compare(s2) == 0; } bool isScramble(string s1, string s2) { size_t len1 = s1.length(); size_t len2 = s2.length(); if (len1 != len2) return false; // Base case: len 1 and 2 if (len1 == 1) return s1 == s2; else if (len1 == 2) return (s1[0] == s2[0] && s1[1] == s2[1]) || (s1[0] == s2[1] && s1[1] == s2[0]); if (s1.compare(s2) == 0) return true; // for (int k = 1; k < len1; k++) { string s11 = s1.substr(0, k); string s12 = s1.substr(k, len1 - k); string s21 = s2.substr(0, k); string s22 = s2.substr(k, len1 - k); if (hasSameLetters(s11, s21) && hasSameLetters(s12, s22)) if (isScramble(s11, s21) && isScramble(s12, s22)) return true; if (hasSameLetters(s11, s22) && hasSameLetters(s12, s21)) if (isScramble(s11, s22) && isScramble(s12, s21)) return true; s21 = s2.substr(0, len2 - k); s22 = s2.substr(len2 - k, k); if (hasSameLetters(s11, s21) && hasSameLetters(s12, s22)) if (isScramble(s11, s21) && isScramble(s12, s22)) return true; if (hasSameLetters(s11, s22) && hasSameLetters(s12, s21)) if (isScramble(s11, s22) && isScramble(s12, s21)) return true; } return false; }};
LeetCode "Scramble String"
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。