字符串习题

Monday, April 20, 2020

字符串

字符串循环移位包含

给定两个字符串 s1,s2,判断s2是否能够被 s1循环移位来包含

func isSubString(_ string: String, _ subString: String) -> Bool {

 var string = string

 string += string

 if string.contains(subString) {

  return  true

 }else {

  return  false

 }

}

字符串循环移位

将字符串右移 k 位,比如 “abcd123” 右移3位,变为“123abcd”

func stringReverse(_ string: String, _ k: Int) -> String {

 let chars = Array(string)

 let leftArray = Array(chars[..<(chars.count - k)]).reversed()

 let rightArray = Array(chars[(chars.count - k)..<chars.count]).reversed()

 print("leftArray:\(leftArray), rightArray: \(rightArray)")

 var array = [Character]()

 array.append(contentsOf: leftArray)

 array.append(contentsOf: rightArray)

 array.reverse()

 return String(array)

}

字符串单词翻转

比如 “I am a student” -> “student a am I”

func reverseWord(_ string: String) -> String {

 var array = Array(string.split(separator: " "))

 array.reverse()

 var str = String()

 for (index, s) in array.enumerated() {

 if index != (s.count - 1) {

 str += s

 str += " "

 }else {

 str += s

 }

 }

 return str

}

两个字符串包含的字符是否完全相同

https://leetcode.com/problems/valid-anagram/description/

用哈希表记录即可,最后对比两个哈希表

    def isAnagram(self, s: str, t: str) -> bool:
    dic1, dic2 = {}, {}
    for c in s:
        dic1[c] = dic1.get(c, 0) + 1
    for c in t:
        dic2[c] = dic2.get(c, 0) + 1
    return dic1 == dic2

计算一组字符集合可以组成的回文字符串的最大长度

https://leetcode.com/problems/longest-palindrome/description/

这题的关键思路也是用哈希表,将字符记录到哈希表之后,把出现的次数 % 2,如果等于0的就把该字母的次数全部加进去,否则尝试减1之后再把该字母的次数加进去。

    def longestPalindrome(self, s: str) -> int:
        dic = {}
        count = 0
        for c in s:
            dic[c] = dic.get(c, 0) + 1
        
        for key in dic:
            if dic[key] % 2 == 0:
                count += dic[key]
            else:
                count += (dic[key] - 1)
        if count < len(s):
            count += 1
        return count

字符串同构

https://leetcode.com/problems/isomorphic-strings/

核心思路还是用哈希表记录,用 key 为 字符串 A 的字符,value 为字符串 B 的字符,遍历字符串,看是不是每个都匹配,如果 key value 不匹配,则不属于同构字符串

    def isIsomorphic(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        dic = {}
        for i in range(len(s)):
            charA = s[i]
            charB = t[i]
            if charA in dic:
                
                if dic[charA] == charB:
                    continue
                else:
                    return False
            else:

                if charB in dic.values():
                    return False
                else:
                    dic[charA] = charB
        return True

回文子字符串个数

https://leetcode.com/problems/palindromic-substrings/description/

因为每一个字符都可以是独立的一个回文字符,所以可以遍历字符串,然后向左和向右扩展,判断是否还是相等(s[start] == s[end]),是相等就 start– , end++,继续判断。

有一点要注意的是,要考虑到偶数情况和奇数情况

    def countSubstrings(self, s: str) -> int:
        count = 0
        for i in range(len(s)):
            //奇数长度
            count = self.extendSubstring(s, i, i, count)
            //偶数长度
            count = self.extendSubstring(s, i, i+1, count)
        return count
        
    
    def extendSubstring(self, s: str, start: int, end: int, count: int) -> int:
        while start >= 0 and end < len(s) and s[start] == s[end]:
            start -= 1
            end += 1
            count += 1
        return count
数据结构-算法LeetCode

HTTPS 介绍

栈和队列