首页 > 代码库 > Leetcode题目总结
Leetcode题目总结
一些不能一次bug-free的题目
Scramble String
"great" -> "rgtae"
方法一:使用分治。需要注意的是前段和后端匹配时候的表达式,不能想当然。
1 public boolean isScramble(String s1, String s2) { 2 if (s1.length() != s2.length()) { 3 return false; 4 } 5 if (s1.equals(s2)){ 6 return true; 7 } 8 int n = s1.length(); 9 int[] chars = new int[26]; 10 for (int i = 0; i < n; i++) { 11 chars[s1.charAt(i) - ‘a‘]++; 12 chars[s2.charAt(i) - ‘a‘]--; 13 } 14 for (int i = 0; i < 26; i++) { 15 if (chars[i] != 0) { 16 return false; 17 } 18 } 19 for (int i = 1; i < n; i++) { 20 if (isScramble(s1.substring(0, i), s2.substring(0, i)) 21 && isScramble(s1.substring(i), s2.substring(i))) { 22 return true; 23 } 24 if (isScramble(s1.substring(0, i), s2.substring(n - i)) && isScramble(s1.substring(i), s2.substring(0, n - i))) { 25 return true; 26 } 27 } 28 return false; 29 }
方法二:很容易注意到这里是可以使用DP的。
Leetcode题目总结
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。