LeetCode--87. Scramble String

本文主要是介绍LeetCode--87. Scramble String，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

87. Scramble String
暴力递归算法：

class Solution {public boolean isScramble(String s1, String s2) {if(s1.length()!=s2.length())return false;if (s1.equals(s2)) return true;int[] record=new int[26];for(int i=0;i<s1.length();i++){record[s1.charAt(i)-'a']++;}for(int i=0;i<s2.length();i++){record[s2.charAt(i)-'a']--;}for(int i=0;i<26;i++){if(record[i]!=0)return false;}for(int i=1;i<s1.length();i++){if( (isScramble(s1.substring(0,i),s2.substring(0,i)) && isScramble(s1.substring(i),s2.substring(i))) ||(isScramble(s1.substring(0,i),s2.substring(s2.length()-i)) && isScramble(s1.substring(i),s2.substring(0,s2.length()-i))))return true;}return false;}

动态规划：

public class Solution {public boolean isScramble(String s1, String s2) {if (s1 == null || s2 == null) return false;int m = s1.length();int n = s2.length();if (m != n) return false;boolean[][][] dp = new boolean[m][m][m+1];for (int i = 0; i < m; i++) {for (int j = 0; j < m; j++) {dp[i][j][1] = s1.charAt(i) == s2.charAt(j);}}for (int k = 2; k <= m; k++) {for (int i = 0; i <= m - k; i++) {for (int j = 0; j <= m - k; j++) {dp[i][j][k] = false;for (int part = 1; part < k; part++) {if ((dp[i][j][l] && dp[i+l][j+l][k-l])|| (dp[i][j+k-l][l] && dp[i+l][j][k-l])) {dp[i][j][k] = true;}}}}}return dp[0][0][s1.length()];}
}

这篇关于LeetCode--87. Scramble String的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---