首页 > 编程语言 >【算法】字符串

【算法】字符串

时间:2023-09-23 12:44:26浏览次数:42  
标签:return self len 算法 str 字符串 def

1 反转字符串

题目:编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间,你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。

1. 双指针

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        left, right = 0, len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

2. 栈

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        stack = []
        for char in s:
            stack.append(char)
        for i in range(len(s)):
            s[i] = stack.pop()

3. 用range

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        n = len(s)
        for i in range(n // 2):
            s[i], s[n - i - 1] = s[n - i - 1], s[i]

4. 切片法**

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s[:] = s[::-1] # s[:]不额外分配内存

5. 列表推导**

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s[:] = [s[i] for i in range(len(s) - 1, -1, -1)]

2 反转字符串II

题目:给定一个字符串 s 和一个整数 k,从字符串开头算起,每计数至 2k 个字符,就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个,则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样。

示例 1:

输入:s = "abcdefg", k = 2
输出:"bacdfeg"

题解

  • 当需要固定规律一段一段去处理字符串的时候,要想想在在for循环的表达式上做做文章。
class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        s = list(s)
        l = len(s)
        for i in range(0, l, 2*k):
            if l - i < k:
                s[i:] = s[i:][::-1]
            else:
                s[i:i+k] = s[i:i+k][::-1]
        return "".join(s)
  • 对于字符串s = 'abc',如果使用s[0: 999] ===> 'abc'。字符串末尾如果超过最大长度,则会返回至字符串最后一个值,这个特性可以避免一些边界条件的处理。
class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        p = 0
        while p < len(s):
            s = s[:p] + s[p:p+k][::-1] + s[p+k:]
            p += 2*k
        return s

3 替换空格

题目:请实现一个函数,把字符串 s 中的每个空格替换成"%20"。

示例 1:

输入:s = "We are happy."
输出:"We%20are%20happy."

思路

1. 转成列表处理

class Solution:
    def replaceSpace(self, s: str) -> str:
        s = list(s)
        for i in range(len(s)):
            if s[i] == " ":
                s[i] = "%20"
        return "".join(s)
class Solution:
    def replaceSpace(self, s: str) -> str:
        return "%20".join(s.split(" "))
class Solution:
    def replaceSpace(self, s: str) -> str:
        return s.replace(' ', '%20')

2. 双指针

首先扩充到每个空格替换成"%20"之后的大小。

然后从后向前替换空格,也就是双指针法,i指向新长度的末尾,j指向旧长度的末尾。

很多填充类的问题,都可以先预先扩容,然后从后向前进行操作。

class Solution:
    def replaceSpace(self, s: str) -> str:
        counter = s.count(' ')
        
        res = list(s)
        # 每碰到一个空格就多拓展两个格子,1 + 2 = 3个位置存’%20‘
        res.extend([' '] * counter * 2)
        
        # 原始字符串的末尾,拓展后的末尾
        left, right = len(s) - 1, len(res) - 1
        
        while left >= 0:
            if res[left] != ' ':
                res[right] = res[left]
                right -= 1
            else:
                # [right - 2, right), 左闭右开
                res[right - 2: right + 1] = '%20'
                right -= 3
            left -= 1
        return ''.join(res)

3. 切片

class Solution:
    def replaceSpace(self, s: str) -> str:
        n = len(s)
        for e, i in enumerate(s[::-1]):
            print(i, e)
            if i == " ":
                s = s[: n - (e + 1)] + "%20" + s[n - e:]
            print("")
        return s

4 反转字符串里的单词

题目:给你一个字符串 s ,请你反转字符串中 单词 的顺序。单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

**注意:**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中,单词间应当仅用单个空格分隔,且不包含任何额外的空格。

示例 1:

输入:s = "the sky is blue"
输出:"blue is sky the"

示例 2:

输入:s = "  hello world  "
输出:"world hello"

思路:先删除空白,然后整个反转,最后单词反转。因为字符串是不可变类型,所以反转单词的时候,需要将其转换成列表,然后通过join函数再将其转换成列表,所以空间复杂度不是O(1)

class Solution:
    def reverseWords(self, s: str) -> str:
        tokens = s.split() # 分割成单词列表
        reverse_tokens = [token for token in tokens][::-1] # 单词列表倒序
        return " ".join(reverse_tokens) # 空格拼接回字符串
class Solution:
    def reverseWords(self, s: str) -> str:
        # 删除前后空白(用split可以省略
        s = s.strip()
        # 反转整个字符串
        s = s[::-1]
        # 将字符串拆分为单词,并反转每个单词
        s = ' '.join(word[::-1] for word in s.split())
        return s

双指针

class Solution:
    def reverseWords(self, s: str) -> str:
        # 将字符串拆分为单词,即转换成列表类型
        words = s.split()
        # 反转单词
        left, right = 0, len(words) - 1
        while left < right:
            words[left], words[right] = words[right], words[left]
            left += 1
            right -= 1
        # 将列表转换成字符串
        return " ".join(words)

5 左旋转字符串

题目:字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串"abcdefg"和数字2,该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1:

输入: s = "abcdefg", k = 2
输出:"cdefgab"

思路:切片过于简单了

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        return s[n:] + s[:n]

提升难度:不能申请额外空间,只能在本串上操作

  1. 反转区间为前n的子串
  2. 反转区间为n到末尾的子串
  3. 反转整个字符串

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        s = list(s)
        s[0:n] = list(reversed(s[0:n]))
        s[n:] = list(reversed(s[n:]))
        s.reverse()
        
        return "".join(s)

reversed() 返回的是一个逆序迭代器,而不是一个列表、字符串或其他序列类型。如果需要将逆序的元素组成一个新的序列(例如列表或字符串),你可以使用 list()''.join() 等方法来转换为所需类型。

  • 用模加下标**
class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        new_s = ''
        for i in range(len(s)):
            j = (i + n) % len(s)
            new_s = new_s + s[j]
        return new_s
  • 拼接加切片**
class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        l = len(s)
        s = s + s     
        return s[n : n + l]

6 找出字符串中第一个匹配项的下标***

题目:给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回  -1 ****。

示例 1:

输入:haystack = "sadbutsad", needle = "sad"
输出:0

示例 2:

输入:haystack = "leetcode", needle = "leeto"
输出:-1

思路

1. KMP模式匹配 **

KMP的经典思想:当出现字符串不匹配时,可以记录一部分之前已经匹配的文本内容,利用这些信息避免从头再去做匹配。

当匹配失败时,模式串上指针j要移动的下一个位置k存在着这样的性质:最前面的k个字符和j之前的最后k个字符是一样的

前缀表:记录下标j之前的字符串中,有多大长度的公共前缀后缀。即:next[j] = k

next[0] = -1; next[1] = 0;

当P[k] == P[j]时,有next[j+1] == next[j] + 1;

当P[k] != P[j]时,k = next[k] (其实就类似于和主串当前字符不一致,要移动到下一个位置)

此外:

上边的算法得到的next数组应该是[ -1,0,0,1 ],下一步我们应该是把j移动到第1个元素。**但这一步是完全没有意义的。因为后面的B已经不匹配了,那前面的B也一定是不匹配的。**显然,发生问题的原因在于P[j] == P[next[j]],所以再添加一个判断条件即可。

class Solution:
    def getNext(self, s: str) -> List[int]:
        j, k = 0, -1
        next = [-1] * len(s)
        while j < len(s) - 1:
            if s[j] == s[k] or k == -1:
                j += 1
                k += 1
                if s[j] == s[k]: # 相同要跳过
                    next[j] = next[k]
                else:
                    next[j] = k
            else:
                k = next[k]
        return next

    def strStr(self, haystack: str, needle: str) -> int:
        if not needle:
            return 0
        next = self.getNext(needle)
        i, j = 0, 0
        while i < len(haystack) and j < len(needle):
            if haystack[i] == needle[j] or j == -1: # j为-1说明要移动i
                i += 1
                j += 1
            else:
                j = next[j]
        if j == len(needle):
            return i - j
        return -1

2. 暴力+切片

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        for i in range(len(haystack)):
            if haystack[i: i + len(needle)] == needle:
                return i
        return -1

3. index法

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle in haystack:
            return haystack.index(needle)
        return -1

4. find法

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        return haystack.find(needle)

7 重复的子字符串**

题目:给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = "aba"
输出: false

示例 2:

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

思路

1. 移动匹配

判断字符串s是否由重复子串组成,只要两个s拼接在一起,里面还出现一个s的话,就说明是由重复子串组成。当然,要刨除 s + s 的首字符和尾字符,这样避免在s+s中搜索出原来的s,我们要搜索的是中间拼接出来的s。

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        new_s = (s + s)[1:-1]
        if s in new_s:
            return True
        return False
class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        new_s = (s + s)[1:-1]
        return new_s.find(s) != -1

2. kmp法**

当一个字符串由重复子串组成的,最长相等前后缀不包含的子串就是最小重复子串。

假设字符串s使用多个重复子串构成(这个子串是最小重复单位),重复出现的子字符串长度是x,所以s是由n * x组成。

因为字符串s的最长相同前后缀的长度一定是不包含s本身,所以 最长相同前后缀长度必然是m * x,而且 n - m = 1,所以如果 nx % (n - m)x = 0,就可以判定有重复出现的子字符串。

如果 next[len - 1] != -1,则说明字符串有最长相同的前后缀(就是字符串里的前缀子串和后缀子串相同的最长长度)。最长相等前后缀的长度为:next[len - 1] + 1

如果len % (len - (next[len - 1] + 1)) == 0 ,则说明数组的长度正好可以被 (数组长度-最长相等前后缀的长度) 整除 ,说明该字符串有重复的子字符串。

数组长度减去最长相同前后缀的长度相当于是第一个周期的长度,也就是一个周期的长度,如果这个周期可以被整除,就说明整个数组就是这个周期的循环。

class Solution:
    def getNext(self, s: str) -> List[int]:
        next = [-1] * len(s)
        j, k = 0, -1
        while j < len(s) - 1:
            if s[j] == s[k] or k == -1:
                j += 1
                k += 1
                next[j] = k
            else:
                k = next[k]
        return next

    def repeatedSubstringPattern(self, s: str) -> bool:
        next = self.getNext(s)
        l = len(s)
        if next[l - 1] != -1 and s[l - 1] == s[next[l - 1]]: # 字符串有最长相同的前后缀
            return l % (l - (next[l - 1] + 1)) == 0
        return False

3. 暴力法

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        for i in range(1, len(s) // 2 + 1):
            if len(s) % i == 0:
                substr = s[:i]
                if substr * (len(s) // i) == s:
                    return True
        return False

标签:return,self,len,算法,str,字符串,def
From: https://www.cnblogs.com/Aikoin/p/17724233.html

相关文章

  • 网络拥塞控制算法总结-PolyCC
    字节跳动在SIGCOMM'23以Poster形式提交了一篇论文《PolyCC:Poly-AlgorithmicCongestionControl》,试图将各种拥塞控制算法整合到一个统一的框架里。其理由是近40年来各种渠道发布的各种拥塞控制算法,没有一种算法能解决所有网络场景(不同的应用,不同的流量模型等)。 如上图,PolyCC......
  • 【Java 基础篇】StringBuilder的魔力:Java字符串处理探究
    在Java编程中,字符串是一个常见的数据类型,用于存储文本信息。然而,与字符串相关的操作可能会导致性能问题,因为字符串是不可变的,每次对字符串进行操作都会创建一个新的字符串对象。为了解决这个问题,Java提供了StringBuilder类,它允许我们有效地处理可变字符串。在本篇博客中,我们将详细......
  • 【Java 基础篇】Java StringBuffer详解:更高效的字符串处理
    在Java编程中,字符串是一个常见的数据类型,用于存储文本信息。然而,与字符串相关的操作可能会导致性能问题,因为字符串是不可变的,每次对字符串进行操作都会创建一个新的字符串对象。为了解决这个问题,Java提供了StringBuffer类,它允许我们有效地处理可变字符串。在本篇博客中,我们将详细讨......
  • 【算法】链表
    1链表理论基础链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。链表的入口节点称为链表的头结点也就是head。链表中的节点在内存中不是连续分布的,而是散乱分布在内......
  • 代码随想录算法训练营-动态规划-1|509. 斐波那契数、70. 爬楼梯
    509. 斐波那契数 1classSolution:2deffib(self,n:int)->int:3ifn<=2:4returnn56prev1,prev2=0,17for_inrange(2,n+1):8sum_value=prev1+prev29prev1,......
  • 【算法】数组
    1数组理论基础数组是存放在连续内存空间上的相同类型数据的集合。数组下标都是从0开始的数组内存空间的地址是连续的在删除或者增添元素时,需要移动其他元素的地址:C++要注意vector和array的区别,vector的底层实现是array,严格来讲vector是容器,不是数组。数组的元素是不能......
  • 代码随想录算法训练营day17 | ● 110.平衡二叉树 ● 257. 二叉树的所有路径 ● 404.
    110.平衡二叉树classSolution{public:intgetHeight(TreeNode*node){if(node==NULL)return0;intleftHeight=getHeight(node->left);if(leftHeight==-1)return-1;intrightHeigh......
  • LZW字典压缩算法及例程
    字典压缩算法是一种数据压缩方法,其基本原理是将重复出现的字符串或者片段用一个短的代表符号来表示,从而减小数据的存储空间。字典压缩算法通常用于无损压缩数据。一种常见的字典压缩算法是Lempel-Ziv-Welch(LZW)算法。该算法通过构建和更新一个字典来实现压缩。初始时,字典中包含......
  • 【算法】算法性能分析
    1时间复杂度1.1知识点时间复杂度是一个函数,它定性描述该算法的运行时间。通常会估算算法的操作单元数量来代表程序消耗的时间。假设算法的问题规模为n,那么操作单元数量便用函数f(n)来表示,随着数据规模n的增大,算法执行时间的增长率和f(n)的增长率相同,这称作为算法的渐近时间复......
  • 【POJ 1521】Entropy 题解(贪心算法+优先队列+哈夫曼树)
    熵编码器是一种数据编码方法,通过对删除了“浪费”或“额外”信息的消息进行编码来实现无损数据压缩。换句话说,熵编码去除了最初不需要的信息,以准确编码消息。高度的熵意味着一条消息包含大量浪费的信息;以ASCII编码的英文文本是具有极高熵的消息类型的示例。已经压缩的消息,如JPEG图......