python code practice（二）：KMP算法、二分搜索的实现、哈希表

https://blog.****.net/starstar1992/article/details/54913261?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task

关于KMP---一个很有名的字符串匹配算法，请参考上面链接学习。

1、替换空格

题目描述：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

分析：

将长度为1的空格替换为长度为3的“%20”，字符串的长度变长。如果允许我们开辟一个新的数组来存放替换空格后的字符串，那么这道题目就非常简单。设置两个指针分别指向新旧字符串首元素，遍历原字符串，如果碰到空格就在新字符串上填入“%20”，否则就复制元字符串上的内容。但是如果面试官要求在原先的字符串上操作，并且保证原字符串有足够长的空间来存放替换后的字符串，那么我们就得另想方法。

class Solution:
    def replaceSpace(self, s):
        s = s.replace(' ', '20%')
        return s

s = Solution()
print(s.replaceSpace('We Are Happy'))

方法2：

首先遍历原字符串，找出字符串的长度以及其中的空格数量，根据原字符串的长度和空格的数量我们可以求出最后新字符串的长度。设置两个指针point1和point2分别指向原字符串和新字符串的末尾位置。（这里为什么取末尾开始遍历，而不是取起始开始遍历，是为了利用point1==point2这个判断条件）如果point1指向内容不为空格，那么将内容赋值给point2指向的位置，如果point1指向为空格，那么从point2开始赋值“02%” 直到point1==point2时表明字符串中的所有空格都已经替换完毕。

class Solution:
    def replaceSpace(self, oldStringList):
        blankNumber = 0 #空格数量
        oldStringLen = len(oldStringList)

        #遍历原字符串,统计字符串中的空格数量
        for i in range(oldStringLen):
            if oldStringList[i] == ' ':
                blankNumber += 1

        #计算新字符串所需要的长度
        newStringLen = oldStringLen + blankNumber*2

        #声明新字符串列表
        newStringList = [' '] * newStringLen

        #设置两个指针，分别指向原字符串和新字符串的末尾位置
        point_old = oldStringLen - 1
        point_new = newStringLen - 1

        #遍历替换
        while point_old != point_new: #如果两个指针位置不同，表示没有替换完成
            if oldStringList[point_old] != ' ':
                newStringList[point_new] = oldStringList[point_old]
                point_old -= 1
                point_new -= 1
            else:
                newStringList[point_new] = '0'
                newStringList[point_new-1] = '2'
                newStringList[point_new-2] = '%'
                point_old -= 1
                point_new -= 3

        #指针恰好相同时，将之前的字符也补上
        if point_old > 0:
            for i in range(point_old, -1, -1):
                newStringList[i] = oldStringList[i]

        #将字符串数组/列表组合为字符串
        newString = ''
        for i in range(newStringLen):
            newString += str(newStringList[i])

        return newString

s = Solution()
print(s.replaceSpace('We Are Happy'))

2、正则表达式匹配

请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配。

这道题需要把题意首先仔细研究清楚。

先分享一个较为清晰的思路：

前提条件：'.'表示任意一个字符；'*'表示它前面的字符可以出现任意次（包含0次）。

首先，考虑特殊情况：

　　1）两个字符串都为空，返回true

　　2）当第一个字符串不空，而第二个字符串空了，返回false（因为这样，就无法匹配成功了,而如果第一个字符串空了，第二个字符串非空，还是可能匹配成功的，比如第二个字符串是“a*a*a*a*”,由于‘*’之前的元素可以出现0次，所以有可能匹配成功）

之后就开始匹配第一个字符，这里有两种可能：匹配成功或匹配失败。但考虑到pattern下一个字符可能是‘*’，这里我们分两种情况讨论：pattern下一个字符为‘*’或不为‘*’：

　　1)pattern下一个字符不为‘*’：

　　这种情况比较简单，直接匹配当前字符。如果匹配成功，继续匹配下一个；如果匹配失败，直接返回false。注意这里的“匹配成功”，除了两个字符相同的情况外，还有一种情况，就是pattern的当前字符为‘.’, 同时str的当前字符不为‘

python code practice（二）：KMP算法、二分搜索的实现、哈希表

相关推荐