前言

本題由于沒有合適答案為以往遺留問題，最近有時間將以往遺留問題一一完善。

我們社區(qū)陸續(xù)會將顧毅（Netflix 增長黑客，《iOS 面試之道》作者，ACE 職業(yè)健身教練。）的 Swift 算法題題解整理為文字版以方便大家學習與閱讀。

LeetCode 算法到目前我們已經更新到 86 期，我們會保持更新時間和進度（周一、周三、周五早上 9:00 發(fā)布），每期的內容不多，我們希望大家可以在上班路上閱讀，長久積累會有很大提升。

不積跬步，無以至千里；不積小流，無以成江海，Swift社區(qū) 伴你前行。如果大家有建議和意見歡迎在文末留言，我們會盡力滿足大家的需求。

難度水平：困難

1. 描述

使用下面描述的算法可以擾亂字符串 s 得到字符串 t ：

1. 如果字符串的長度為 1 ，算法停止
2. 如果字符串的長度 > 1 ，執(zhí)行下述步驟：
   • 在一個隨機下標處將字符串分割成兩個非空的子字符串。即，如果已知字符串 s ，則可以將其分成兩個子字符串 x 和 y ，且滿足 s = x + y 。
   • 隨機 決定是要「交換兩個子字符串」還是要「保持這兩個子字符串的順序不變」。即，在執(zhí)行這一步驟之后，s 可能是 s = x + y 或者 s = y + x 。
   • 在 x 和 y 這兩個子字符串上繼續(xù)從步驟 1 開始遞歸執(zhí)行此算法。

給你兩個 長度相等 的字符串 s1 和 s2，判斷 s2 是否是 s1 的擾亂字符串。如果是，返回 true ；否則，返回 false 。

2. 示例

示例 1

輸入：s1 = "great", s2 = "rgeat"
輸出：true
解釋：s1 上可能發(fā)生的一種情形是：
"great" --> "gr/eat" // 在一個隨機下標處分割得到兩個子字符串
"gr/eat" --> "gr/eat" // 隨機決定：「保持這兩個子字符串的順序不變」
"gr/eat" --> "g/r / e/at" // 在子字符串上遞歸執(zhí)行此算法。兩個子字符串分別在隨機下標處進行一輪分割
"g/r / e/at" --> "r/g / e/at" // 隨機決定：第一組「交換兩個子字符串」，第二組「保持這兩個子字符串的順序不變」
"r/g / e/at" --> "r/g / e/ a/t" // 繼續(xù)遞歸執(zhí)行此算法，將 "at" 分割得到 "a/t"
"r/g / e/ a/t" --> "r/g / e/ a/t" // 隨機決定：「保持這兩個子字符串的順序不變」
算法終止，結果字符串和 s2 相同，都是 "rgeat"
這是一種能夠擾亂 s1 得到 s2 的情形，可以認為 s2 是 s1 的擾亂字符串，返回 true

示例 2

輸入：s1 = "abcde", s2 = "caebd"
輸出：false

示例 3

輸入：s1 = "a", s2 = "a"
輸出：true

提示：

• s1.length == s2.length
• 1 <= s1.length <= 30
• s1 和 s2 由小寫英文字母組成

3. 答案

題解 1

class Solution {
   func isScramble(_ s1: String, _ s2: String) -> Bool {
       if s1 == s2 {
           return true
       }

       var letters = [Int](repeating: 0, count: 26)

       for i in 0..<s1.count {
           let aASCII = Character("a").ascii
           letters[s1[i].ascii - aASCII] += 1
           letters[s2[i].ascii - aASCII] -= 1
       }
       for i in 0..<26 {
           if letters[i] != 0 {
               return false
           }
       }
       for i in 1..<s1.count {
           if isScramble(s1[0..<i], s2[0..<i]) &&
               isScramble(s1[i..<s1.count], s2[i..<s2.count]) {
               return true
           }
           if isScramble(s1[0..<i], s2[(s2.count - i)..<s2.count]) &&
               isScramble(s1[i..<s1.count], s2[0..<(s2.count - i)]) {
               return true
           }
       }

       return false
   }
}

extension String {
   subscript (i: Int) -> Character {
       return self[index(startIndex, offsetBy: i)]
   }

   subscript(_ range: CountableRange<Int>) -> String {
       let idx1 = index(startIndex, offsetBy: max(0, range.lowerBound))
       let idx2 = index(startIndex, offsetBy: min(self.count, range.upperBound))
       return String(self[idx1..<idx2])
   }
}

extension Character {
   var ascii: Int {
       get {
           let s = String(self).unicodeScalars
           return Int(s[s.startIndex].value)
       }
   }

   func isDigit() -> Bool {
       return self >= "0" && self <= "9"
   }
}

點擊前往 LeetCode 練習

關于我們

我們是由 Swift 愛好者共同維護，我們會分享以 Swift 實戰(zhàn)、SwiftUI、Swift 基礎為核心的技術內容，也整理收集優(yōu)秀的學習資料。文章來源地址http://www.zghlxwxcb.cn/news/detail-735000.html

到了這里，關于LeetCode - #87 擾亂字符串的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！