• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode1147.段式回文|LongestChunkedPalindromeDecomposition

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(let_us_code)
➤博主域名:https://www.zengqiang.org
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Return the largest possible k such that there exists a_1, a_2, ..., a_k such that:

  • Each a_i is a non-empty string;
  • Their concatenation a_1 + a_2 + ... + a_k is equal to text;
  • For all 1 <= i <= k,  a_i = a_{k+1 - i}

Example 1:

Input: text = "ghiabcdefhelloadamhelloabcdefghi"
Output: 7
Explanation: We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".

Example 2:

Input: text = "merchant"
Output: 1
Explanation: We can split the string on "(merchant)".

Example 3:

Input: text = "antaprezatepzapreanta"
Output: 11
Explanation: We can split the string on "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)".

Example 4:

Input: text = "aaa"
Output: 3
Explanation: We can split the string on "(a)(a)(a)". 

Constraints:

  • text consists only of lowercase English characters.
  • 1 <= text.length <= 1000

段式回文 其实与 一般回文 类似,只不过是最小的单位是 一段字符 而不是 单个字母。

举个例子,对于一般回文 "abcba" 是回文,而 "volvo" 不是,但如果我们把 "volvo" 分为 "vo"、"l"、"vo" 三段,则可以认为 “(vo)(l)(vo)” 是段式回文(分为 3 段)。 

给你一个字符串 text,在确保它满足段式回文的前提下,请你返回 段 的 最大数量 k

如果段的最大数量为 k,那么存在满足以下条件的 a_1, a_2, ..., a_k

  • 每个 a_i 都是一个非空字符串;
  • 将这些字符串首位相连的结果 a_1 + a_2 + ... + a_k 和原始字符串 text 相同;
  • 对于所有1 <= i <= k,都有 a_i = a_{k+1 - i}。 

示例 1:

输入:text = "ghiabcdefhelloadamhelloabcdefghi"
输出:7
解释:我们可以把字符串拆分成 "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)"。

示例 2:

输入:text = "merchant"
输出:1
解释:我们可以把字符串拆分成 "(merchant)"。

示例 3:

输入:text = "antaprezatepzapreanta"
输出:11
解释:我们可以把字符串拆分成 "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)"。

示例 4:

输入:text = "aaa"
输出:3
解释:我们可以把字符串拆分成 "(a)(a)(a)"。 

提示:

  • text 仅由小写英文字符组成。
  • 1 <= text.length <= 1000

8ms
 1 class Solution {
 2     func longestDecomposition(_ text: String) -> Int {
 3         var result = 0
 4         var chars = Array(text)
 5         var n = text.count
 6         var l = ""
 7         var r = ""
 8         for i in 0..<n {
 9             l += String(chars[i])
10             r = String(chars[n-i-1]) + r
11             if l == r {
12                 result += 1
13                 l = ""
14                 r = ""
15             }
16         }
17         return result
18     }
19 }

Runtime: 12 ms

Memory Usage: 20.6 MB
 1 class Solution {
 2     func longestDecomposition(_ text: String) -> Int {
 3         let n:Int = text.count
 4         for i in 0..<(n/2)
 5         {
 6             if text.subString(0, i + 1) == (text.subString(n - 1 - i, n))
 7             {
 8                 return 2 + longestDecomposition(text.subString(i + 1, n - 1 - i))
 9             }
10         }
11         return (n == 0) ? 0 : 1
12     }
13 }
14 extension String {
15     // 截取字符串:指定索引和字符数
16     // - star: 开始索引
17     // - end: 结束索引
18     func subString(_ start:Int,_ end:Int) -> String {
19         let start = self.index(self.startIndex, offsetBy: start)
20         let end = self.index(self.startIndex, offsetBy: end)
21         return String(self[start..<end]) 
22     }
23 }

12ms 
 1 class Solution {
 2     func longestDecomposition(_ text: String) -> Int {
 3         let chars = Array(text)
 4         var l = chars.startIndex
 5         var r = chars.endIndex - 1
 6         let mid = (l + r + 1) / 2
 7         var ans = 0
 8         
 9         while l < r {
10             let range = 0..<mid-l
11             var next  = range.upperBound
12             for i in range where chars[l...l+i] == chars[r-i...r] {
13                 next = i + 1
14                 ans += 2
15                 if l + i + 1 == r - i {
16                     return ans
17                 }else{
18                     break
19                 }
20             }
21             l += next
22             r -= next
23         }
24         return ans + 1
25     }
26 }

16ms

 1 class Solution {
 2     func longestDecomposition(_ text: String) -> Int {
 3         let s = Array(text)
 4         var result = 0
 5         
 6         let end = s.endIndex - 1
 7         var i = s.startIndex
 8         var j = s.startIndex
 9         
10         //ghiabcdefhelloadamhelloabcdefghi
11         while i <= end{
12             while j <= end {
13                 let range1 = i...(i+j)
14                 let range2 = (end-i-j)...(end-i)
15                 j += 1
16                 guard s[range1] == s[range2] else { continue }
17                 result += 1
18                 break
19             }
20         
21             i += j
22             j = 0
23         }
24         return result
25     }
26 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[Swift]LeetCode1286.字母组合迭代器|IteratorforCombination发布时间:2022-07-13
下一篇:
swift语法和java的比较发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap