[Swift]LeetCode1177.构建回文串检测|CanMakePalindromefromSubstring

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

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

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a string s, we make queries on substrings of s.

For each query queries[i] = [left, right, k], we may rearrange the substring s[left], ..., s[right], and then choose up to k of them to replace with any lowercase English letter.

If the substring is possible to be a palindrome string after the operations above, the result of the query is true. Otherwise, the result is false.

Return an array answer[], where answer[i] is the result of the i-th query queries[i].

Note that: Each letter is counted individually for replacement so if for example s[left..right] = "aaa", and k = 2, we can only replace two of the letters. (Also, note that the initial string s is never modified by any query.)

Example :

Input: s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
Output: [true,false,false,true,true]
Explanation:
queries[0] : substring = "d", is palidrome.
queries[1] : substring = "bc", is not palidrome.
queries[2] : substring = "abcd", is not palidrome after replacing only 1 character.
queries[3] : substring = "abcd", could be changed to "abba" which is palidrome. Also this can be changed to "baab" first rearrange it "bacd" then replace "cd" with "ab".
queries[4] : substring = "abcda", could be changed to "abcba" which is palidrome.

Constraints:

1 <= s.length, queries.length <= 10^5
0 <= queries[i][0] <= queries[i][1] < s.length
0 <= queries[i][2] <= s.length
s only contains lowercase English letters.

给你一个字符串 s，请你对 s 的子串进行检测。

每次检测，待检子串都可以表示为 queries[i] = [left, right, k]。我们可以重新排列子串 s[left], ..., s[right]，并从中选择最多 k 项替换成任何小写英文字母。

如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为 true，否则结果为 false。

返回答案数组 answer[]，其中 answer[i] 是第 i 个待检子串 queries[i] 的检测结果。

注意：在替换时，子串中的每个字母都必须作为独立的项进行计数，也就是说，如果 s[left..right] = "aaa" 且 k = 2，我们只能替换其中的两个字母。（另外，任何检测都不会修改原始字符串 s，可以认为每次检测都是独立的）

示例：

输入：s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
输出：[true,false,false,true,true]
解释：
queries[0] : 子串 = "d"，回文。
queries[1] : 子串 = "bc"，不是回文。
queries[2] : 子串 = "abcd"，只替换 1 个字符是变不成回文串的。
queries[3] : 子串 = "abcd"，可以变成回文的 "abba"。 也可以变成 "baab"，先重新排序变成 "bacd"，然后把 "cd" 替换为 "ab"。
queries[4] : 子串 = "abcda"，可以变成回文的 "abcba"。

提示：

1 <= s.length, queries.length <= 10^5
0 <= queries[i][0] <= queries[i][1] < s.length
0 <= queries[i][2] <= s.length
s 中只有小写英文字母

Runtime: 1204 ms

Memory Usage: 55.4 MB

 1 class Solution {
 2     func canMakePaliQueries(_ s: String, _ queries: [[Int]]) -> [Bool] {
 3         var s:[Int] = Array(s).map{$0.ascii}
 4         var n:Int = s.count
 5         var m:Int = queries.count
 6         var res:[Bool] = [Bool](repeating:false,count:m)
 7         var sum:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:26),count:n)
 8         for i in 0..<n
 9         {
10             if i > 0
11             {
12                 sum[i] = sum[i-1]
13             }
14             sum[i][s[i] - 97] += 1
15         }
16         for i in 0..<m
17         {
18             var l:Int = queries[i][0]
19             var r:Int = queries[i][1]
20             var k:Int = queries[i][2]
21             var cnt:Int = 0
22             for j in 0..<26
23             {
24                 var tmp:Int = sum[r][j]
25                 if l > 0
26                 {
27                     tmp -= sum[l-1][j]
28                 }
29                 
30                 if tmp & 1 != 0
31                 {
32                     cnt += 1
33                 }
34             }
35             if (r-l+1) & 1 != 0
36             {
37                 cnt -= 1
38             }
39             res[i] = cnt <= k * 2
40         }
41         return res
42     }
43 }
44 
45 //Character扩展 
46 extension Character  
47 {  
48   //Character转ASCII整数值(定义小写为整数值)
49    var ascii: Int {
50        get {
51            return Int(self.unicodeScalars.first?.value ?? 0)
52        }       
53     }
54 }

1328ms

 1 class Solution {
 2     func canMakePaliQueries(_ s: String, _ queries: [[Int]]) -> [Bool] {
 3         let s = Array(s.utf8)
 4         var freqs = [Freq]()
 5         var freq = Freq()
 6         freqs.append(freq)
 7         for char in s {
 8             let f = Freq(freq, char)
 9             freqs.append(f)
10             freq = f
11         }
12         
13         var res = [Bool]()
14         for query in queries {
15             res.append(solve(query, freqs))
16         }
17         
18         return res
19     }
20     
21     func solve(_ query: [Int], _ freqs: [Freq]) -> Bool {
22         let freq1 = freqs[query[0]]
23         let freq2 = freqs[query[1] + 1]
24         let num = query[2]
25         let freq = freq1 - freq2
26         var countOdd = 0
27         for i in 0..<26 {
28             if freq.arr[i] % 2 == 1 {
29                 countOdd += 1
30             }
31         }
32         //print(freq, countOdd, num)
33         return (countOdd - num * 2) <= 1
34     }
35 }
36 
37 struct Freq {
38     var arr: [Int]
39     
40     init() {
41         arr = [Int](repeating: 0, count:  26)
42     }
43     
44     init(_ freq: Freq, _ char: UInt8) {
45         self.arr = freq.arr
46         arr[Int(char) - 97] += 1
47     }
48     
49     init(_ str: [UInt8]) {
50         arr = [Int](repeating: 0, count:  26)
51         for char in str {
52             arr[Int(char) - 97] += 1
53         }
54     }
55     
56     static func -(lhs: Freq, rhs: Freq) -> Freq {
57         var freq = Freq()
58         for i in 0..<26 {
59             freq.arr[i] = rhs.arr[i] - lhs.arr[i]
60         }
61         return freq
62     }
63 }

1452ms

 1 class Solution {
 2     func canMakePaliQueries(_ s: String, _ queries: [[Int]]) -> [Bool] {   
 3         let chars = Array(s), n = chars.count
 4         let table = Array("abcdefghijklmnopqrstuvwxyz")
 5         var freq = [[Int]](repeating: [Int](repeating: 0, count: n+1), count: 26)
 6         for c in 0..<26 {
 7             for i in 0..<n {
 8                 freq[c][i+1] = freq[c][i] + (chars[i] == table[c] ? 1 : 0)
 9             }
10         }
11         var ans = [Bool]()
12         for que in queries {
13             var i = que[0], j = que[1], k = que[2]
14             j += 1
15             var odd_count = 0
16             for c in 0..<26 where (freq[c][j] - freq[c][i])%2 != 0 {
17                 odd_count += 1
18             }
19 
20             let fullfill = (odd_count-1) <= 2*k
21             ans.append(fullfill)
22         }
23         return ans
24     }
25 }