Tate Blog

iOS Developer

0%

Swift Leetcode 字符串 算法题解

Posted on In

1.字符串轮转

字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。

示例1:

输入：s1 = “waterbottle”, s2 = “erbottlewat”
输出：True
示例2:

输入：s1 = “aa”, s2 = “aba”
输出：False
提示：

字符串长度在[0, 100000]范围内。
说明:

你能只调用一次检查子串的方法吗？

1
2
3
4
5
6
7
class Solution {
    func isFlipedString(_ s1: String, _ s2: String) -> Bool {
        if s1 == "" && s2 == "" { return true } //处理空字符串
        guard s1.count == s2.count else {return false}
        return (s1 + s1).contains(s2)
    }
}

解题思路：

  1. 利用s1+s1拼接起来，这样子就包括所有的旋转字符串了
  2. 只要新的字符串包含s2直接返回true

2.另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例

img

1
2
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

提示：

root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-104 <= root.val <= 104
-104 <= subRoot.val <= 104

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func isSubtree(_ root: TreeNode?, _ subRoot: TreeNode?) -> Bool {
        guard root != nil && subRoot != nil else {return false}
        return postSerialize(root).contains(postSerialize(subRoot)) //只要包含就代表是子树
    }

    //使用后序遍历树序列化
    func postSerialize(_ root: TreeNode?) -> String{
        guard root != nil else {return "#!"}
        var res = ""
        res += postSerialize(root?.left)
        res += postSerialize(root?.right)
        if let s = root?.val {
            res.append("\(s)!")
        }
        return res
    }
}

解题思路：

我们可以想到用字符串包含的关系来解出这道题

  1. 使用后续遍历，这里前序中序都是可以的，根据”!”格式划分出每个node的值,空值就用#代替
  2. 序列化成字符串，那基树的序列化字符串肯定要包含子树的序列化字符串才算是它的子树
  3. 直接判断是否包含，问题迎刃而解

3.有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

输入: s = “anagram”, t = “nagaram”
输出: true
示例 2:

输入: s = “rat”, t = “car”
输出: false

提示:

1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    func isAnagram(_ s: String, _ t: String) -> Bool {
        //不相等直接返回
        guard s.count == t.count else {return false}
        //字符串最多只有26个小写字母
        var record = [Int](repeating: 0, count: 26)
        let aUni = "a".unicodeScalars.first!.value //ASCll码表对应 97
        
        for uniCode in s.unicodeScalars{
            record[Int(uniCode.value - aUni)] += 1
        }
        
        for uniCode in t.unicodeScalars{
            let index = Int(uniCode.value - aUni)
            record[index] -= 1
            //只要有对应的字符为 -1 代表不是有效的字母异位词
            if record[index] < 0 {
                return false
            }
        }
        
        return true
    }
}

解题思路：

  1. 题目有个提示s 和 t 仅包含小写字母，那就是只有26个小写字母
  2. 我们可以想到用哈希表来一一对应
  3. 使用”a”ASCll码表对应 97 用它来做起点，把所有的26个小写字母转化为ASCll码去减得到对应的索引值
  4. 遍历第一个s字符串，出现就++，再次遍历t字符串，出现就–，如果一旦有索引值为-1代表不是有效的字母异位词

4.最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。
示例 2：

输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc” ，它的长度为 3 。
示例 3：

输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
        guard text1.count != 0 && text2.count != 0 else {return 0}

        return lcs(Array(text1), text1.count, Array(text2), text2.count)
    }

    func lcs(_ arr1: [Character],_ i:Int, _ arr2: [Character],_ j:Int) -> Int {
       guard i != 0 && j != 0 else {return 0} //只要最短的字符串数组为0就停止递归
       
       if arr1[i - 1] == arr2[j - 1] {
           return lcs(arr1, i - 1, arr2, j-1) + 1
       }
       
       return max(lcs(arr1, i - 1, arr2, j),lcs(arr1, i, arr2, j-1))
   }
}

解题思路：

  1. 这里才用了递归解法，虽说能算出结果，但是时间复杂度已经达到了On^2次方,所以我们应该有动态规划（dp）来解题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
        guard text1.count != 0 && text2.count != 0 else {return 0}
        let arr1 = Array(text1)
        let arr2 = Array(text2)
        let n = arr1.count
        let m = arr2.count
        //创建动态规划二维数组
        var dp = [[Int]](repeating: [Int](repeating: 0, count: m + 1), count: n + 1)
        for i in 1...arr1.count { //注意这里包括arr1.count
            for j in 1...arr2.count { //注意这里包括arr1.count
                if arr1[i - 1] == arr2[j - 1] { //这里开始是1所以需要-1去比较
                    dp[i][j] =  dp[i - 1][j - 1] + 1 //只要相等就 + 1
                }else{
                    dp[i][j] =  max(dp[i - 1][j],dp[i][j - 1]) //取最大值
                }
            }
        }
        //为了能dp[n][m] 所以创建二维数组需要 dp[n + 1][m + 1]
        return dp[n][m]
   }
}

解题思路：

空间复杂度：O( n * m )
时间复杂度：O( n * m )

  1. 这里使用dp二维数组来推导出每个dp[i][j]对应的最长公共子序列
  2. 具体细节可以看代码注释
  3. 难道这里就是最优解法吗？当然不是还有对空间复杂度进行优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
        guard text1.count != 0 && text2.count != 0 else {return 0}
        let arr1 = Array(text1)
        let arr2 = Array(text2)
        var rowsChars = arr1
        var colsChars = arr2
        if (arr1.count < arr2.count) {
            colsChars = arr1
            rowsChars = arr2
        }
        var dp = [Int](repeating: 0, count: colsChars.count + 1) //使用一维数组 + 一个变量
        for i in 1...rowsChars.count {
            var cur = 0 //记录leftTop用来动态规划推断出rowsChars[i - 1] == colsChars[j - 1相等的情况
            for j in 1...colsChars.count {
                let leftTop = cur
                cur = dp[j]
                if (rowsChars[i - 1] == colsChars[j - 1]) {
                    dp[j] = leftTop + 1
                } else {
                    dp[j] = max(dp[j], dp[j - 1])
                }
            }
        }
        return dp[colsChars.count]
    }
}

这里的空间复杂度可以优化到极致，只需要使用一维数组 + 一个变量即可推出结果

5.翻转字符串里的单词

给你一个字符串 s ，逐个翻转字符串中的所有 单词 。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

说明：

输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
翻转后单词间应当仅用一个空格分隔。
翻转后的字符串中不应包含额外的空格。

示例 1：

输入：s = “the sky is blue”
输出：”blue is sky the”
示例 2：

输入：s = “ hello world “
输出：”world hello”
解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。
示例 3：

输入：s = “a good example”
输出：”example good a”
解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。
示例 4：

输入：s = “ Bob Loves Alice “
输出：”Alice Loves Bob”
示例 5：

输入：s = “Alice does not even like bob”
输出：”bob like even not does Alice”

提示：

1 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ‘ ‘
s 中 至少存在一个 单词

进阶：

请尝试使用 O(1) 额外空间复杂度的原地解法。

1
func

6.无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成