手工实现字符串 replace 方法

字符串、双指针

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

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

示例 1：

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

限制：0 <= s 的长度 <= 10000

直觉

这种重写基础方法的问题，可以先用现有的内建方法实现一下，然后在其基础上改写自己的方法。 1、无脑调用 python字符串的replace方法 2、基于Python字符串 splite 方法 和 join 方法 解决 3、不依赖任何Python内建函数实现 replace（多一层函数栈调用，性能就会下降一点。） 4、以上都是从前往后遍历，由于是基于Python的，所以做字符串操作比较简单，时间复杂度是 \(O(n)\)。但是如果是C++来实现这个代码，从前往后遍历的时间复杂度就是 \(O(n^2)\)，看了《剑指offer》这本书之后，书中提到了一个思路，是从后往前遍历，无论用哪一种语言，时间复杂度都是 \(O(n)\)。

1. 从' '到'%20'增加了2位，如果有n个空格，就会增加n*2的位置。
2. 将长度为len的字符串，增加到长度为len + 2*n，新增的2*n的位置为' '
3. 双指针P1指向字符串末尾，在前。P2指向新增长度末尾，在后。
4. 同时前移P1和P2且将P1位置的字符复制到P2位置，当碰到P1空格时，P1往前移动一格，P2往前移动3格。在这三格分别填充'%'、'2'、'0'。
5. 一直往前移动，直到P2赶上P1，即可结束。

注意这几种特殊情况，"cad eaeb", "a b", "a b ", " a b", " ", ""。

代码

1、无脑调用 python字符串的replace方法

class Solution:
    def replaceSpace(self, s: str) -> str:
        return s.replace(" ", "%20")

2、基于Python字符串 splite 方法 和 join 方法 解决

class Solution:
    def replaceSpace(self, s: str) -> str:
        s = s.split(" ")
        return '%20'.join(s)

3、不依赖任何Python内建函数实现 replace

class Solution:
    def split(self, target, s):
        """ split str according special divider
        :param target: str
        :param s: str
        :return: list
        """
        start = 0
        segments = []
        for i in range(len(s)):
            if s[i] == target:
                segments.append(s[start:i])
                start = i + 1
        segments.append(s[start:])
        return segments

    def join(self, link, lists):
        """join items in the list by special linker
        :param link: str
        :param lists: list
        :return: str
        """
        res = ''
        for i in lists:
            res += (i+link)
        if len(link):
            res = res[:-len(link)]
        return res

    def replace(self, target, replce, string):
        """replace character in the str with anoteher charcter
        :param target: str
        :param replace: str
        :param string: str
        :return: str
        """
        segments = self.split(target, string)
        res = self.join(replce, segments)
        return res

    def replaceSpace(self, s: str) -> str:
        return self.replace(' ', '%20', s)

4、从后往前遍历

import unittest

class Solution:
    def replaceSpace(self, s: str) -> str:
        # 特判输入字符为''的情况
        if not len(s):  return ''
        padding = '%20'
        # 1. 从' '到'%20'增加了2位，如果有n个空格，就会增加n*2的位置。
        count = 0
        for i in s:
            if i == ' ':
                count += 1
        # 2. 将长度为len的字符串，增加到长度为len + 2*n，新增的2*n的位置为' '
        p1 = len(s) - 1
        s += ' ' * count * 2
        # 3. 双指针P1指向字符串末尾，在前。P2指向新增长度末尾，在后。
        p2 = len(s) - 1
        # 5. 一直往前移动，直到P2赶上P1，即可结束。
        s = list(s)  # 由于str是不可变对象，所以要先转换成list
        while p1 != p2 or (s[p1] == ' ' and s[p2] == ' '):  # 排除空格位于字符串最前面、最后面、中间连续位置的情况
            # 4. 同时前移P1和P2且将P1位置的字符复制到P2位置
            if s[p1] != " ":
                s[p2] = s[p1]
                p1 -= 1
                p2 -= 1
            else:  # 当碰到P1空格时，P1往前移动一格，P2往前移动3格。在这三格分别填充'%'、'2'、'0'。
                p1 -= 1
                for i in range(2, -1, -1):
                    s[p2] = padding[i]
                    p2 -= 1
        return "".join(s)

class TestSulotion(unittest.TestCase):
    """声明Python UnitTest Class用于测试
    """
    def setUp(self):
        self.test_class = Solution()

    def test_replaceSpace(self):
        s = ["cad eaeb", "a   b", "a b  ", "  a b", "     ", "We are happy.", ""]
        answer = ["cad%20eaeb", "a%20%20%20b", "a%20b%20%20", "%20%20a%20b", "%20%20%20%20%20", "We%20are%20happy.", ""]
        for i in range(len(s)):
            self.assertEqual(self.test_class.replaceSpace(s[i]), answer[i])

    def tearDown(self):
        del self.test_class


if __name__ == "__main__":
    # 简单测试的方法
    unittest.main()