Description

https://leetcode.com/problems/scramble-string/
給定兩個字符串s1，s2，判斷s2是否為s1的Scramble String

Solving Ideas

https://leetcode.com/problems/scramble-string/discuss/29387/Accepted-Java-solution
遞歸遍歷全部可能的結果

時間復雜度：$O(n!)$
空間復雜度：$O(n)$

Solution

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

總結

以上是生活随笔為你收集整理的87. Scramble String的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。