LeetCode - #87 扰乱字符串

这篇具有很好参考价值的文章主要介绍了LeetCode - #87 扰乱字符串。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

LeetCode - #87 扰乱字符串,# LeetCode,leetcode,算法,职场和发展,原力计划

LeetCode - #87 扰乱字符串,# LeetCode,leetcode,算法,职场和发展,原力计划

前言

本题由于没有合适答案为以往遗留问题,最近有时间将以往遗留问题一一完善。

我们社区陆续会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。)的 Swift 算法题题解整理为文字版以方便大家学习与阅读。

LeetCode 算法到目前我们已经更新到 86 期,我们会保持更新时间和进度(周一、周三、周五早上 9:00 发布),每期的内容不多,我们希望大家可以在上班路上阅读,长久积累会有很大提升。

不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。

难度水平:困难

1. 描述

使用下面描述的算法可以扰乱字符串 s 得到字符串 t

  1. 如果字符串的长度为 1 ,算法停止
  2. 如果字符串的长度 > 1 ,执行下述步骤:
    • 在一个随机下标处将字符串分割成两个非空的子字符串。即,如果已知字符串 s ,则可以将其分成两个子字符串 xy ,且满足 s = x + y
    • 随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即,在执行这一步骤之后,s 可能是 s = x + y 或者 s = y + x
    • xy 这两个子字符串上继续从步骤 1 开始递归执行此算法。

给你两个 长度相等 的字符串 s1s2,判断 s2 是否是 s1 的扰乱字符串。如果是,返回 true ;否则,返回 false

2. 示例

示例 1

输入:s1 = "great", s2 = "rgeat"
输出:true
解释:s1 上可能发生的一种情形是:
"great" --> "gr/eat" // 在一个随机下标处分割得到两个子字符串
"gr/eat" --> "gr/eat" // 随机决定:「保持这两个子字符串的顺序不变」
"gr/eat" --> "g/r / e/at" // 在子字符串上递归执行此算法。两个子字符串分别在随机下标处进行一轮分割
"g/r / e/at" --> "r/g / e/at" // 随机决定:第一组「交换两个子字符串」,第二组「保持这两个子字符串的顺序不变」
"r/g / e/at" --> "r/g / e/ a/t" // 继续递归执行此算法,将 "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
  • s1s2 由小写英文字母组成

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 实战、SwiftUI、Swift 基础为核心的技术内容,也整理收集优秀的学习资料。文章来源地址https://www.toymoban.com/news/detail-735000.html

到了这里,关于LeetCode - #87 扰乱字符串的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法之字符串: Leetcode 557. 反转字符串中的单词 III (Typescript版)

    翻转字符串中的单词 III https://leetcode.cn/problems/reverse-words-in-a-string-iii/ 描述 给定一个字符串 s ,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。 示例 1: 示例 2: 提示: 1 = s.length = 5 * 1 0 4 10^4 1 0 4 s 包含可打印的 ASCII 字符。 s 不包含任何开头或

    2024年02月01日
    浏览(77)
  • 代码随想录 Leetcode459. 重复的子字符串(KMP算法)

            此解法读者需要了解什么是KMP算法以及KMP算法中next数组的具体含义才能理解         因为在KMP算法的next数组中,next[index]表示 i ndex之前的最大长度的相同前缀后缀值 ,那么要判断整个字符串中是否由重复字串构成,只需要以下两个条件:         1.next[n - 1] !=

    2024年01月19日
    浏览(79)
  • 【动态规划】【字符串】扰乱字符串

    视频算法专题 动态规划汇总 字符串 使用下面描述的算法可以扰乱字符串 s 得到字符串 t : 如果字符串的长度为 1 ,算法停止 如果字符串的长度 1 ,执行下述步骤: 在一个随机下标处将字符串分割成两个非空的子字符串。即,如果已知字符串 s ,则可以将其分成两个子字符

    2024年02月03日
    浏览(60)
  • 【编码狂想】LeetCode 字符串和数组篇:挑战算法精髓,深化程序设计基础

    ​ 🌈 个人主页: Sarapines Programmer  🔥 系列专栏: 本期文章收录在《C语言闯关笔记》,大家有兴趣可以浏览和关注,后面将会有更多精彩内容!  ⏰翰墨致赠:翩翩风华激彩虹,豪情壮志醉长空。 剑指星河舞红尘,梦驰烈马向未来。 ​ ​ 🎉欢迎大家关注🔍点赞👍收藏

    2024年02月04日
    浏览(52)
  • 数据结构与算法之字符串: Leetcode 20. 有效的括号 (Typescript版)

    有效的括号 https://leetcode.cn/problems/valid-parentheses/ 描述 给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相

    2024年02月01日
    浏览(54)
  • 数据结构与算法之字符串: Leetcode 696. 计数二进制子串 (Typescript版)

    计数二进制子串 https://leetcode.cn/problems/count-binary-substrings/ 描述 给定一个字符串 s,统计并返回具有相同数量 0 和 1 的非空(连续)子字符串的数量,并且这些子字符串中的所有 0 和所有 1 都是成组连续的。 重复出现(不同位置)的子串也要统计它们出现的次数。 示例 1: 示

    2024年02月01日
    浏览(60)
  • 【算法|动态规划No.28】leetcode1312. 让字符串成为回文串的最少插入次数

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月06日
    浏览(57)
  • 算法训练day11Leetcode20有效的括号1047删除字符串中所有相邻重复项150逆波兰表达式求值

    https://leetcode.cn/problems/valid-parentheses/description/ https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html 判断右括号后忘记pop 括号匹配是使用栈解决的经典问题。 如果还记得编译原理的话,编译器在 词法分析的过程中处理括号、花括号等这个符号的逻辑,也是使用了栈

    2024年01月17日
    浏览(76)
  • ( 字符串) 205. 同构字符串 ——【Leetcode每日一题】

    难度:简单 给定两个字符串 s 和 t ,判断它们是否是同构的。 如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的。 每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序。不同字符不能映射到同一个字符上,相同字符只能映射到同一个

    2024年02月02日
    浏览(55)
  • 【LeetCode】《LeetCode 101》第十二章:字符串

    思路及代码: 242 . 有效的字母异位词 思路及代码: 205. 同构字符串 思路及代码: 647. 回文子串 思路及代码: 696 . 计数二进制子串 思路及代码 : 224. 基本计算器 思路及代码: 227. 基本计算器 II 思路与代码: 28 . 找出字符串中第一个匹配项的下标 思路及代码 :409. 最长回文

    2024年02月10日
    浏览(84)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包