字符串高频面试题目

Posted on by mindthink

目录

确定字符互异

请实现一个算法，确定一个字符串的所有字符是否全都不同。这里我们要求不允许使用额外的存储结构。
给定一个string iniString，请返回一个bool值,True代表所有字符全都不同，False代表存在相同的字符。保证字符串中的字符为ASCII字符。字符串的长度小于等于3000。
测试样例：

"aeiou"

返回：True

BarackObama"

返回：False

解题思路

使用集合能自动去重，然后判断set（）前和set()后长度是否一样，如果一样，则没有重复的字符。

# -*- coding:utf-8 -*-
class Different:
    def checkDifferent(self, iniString):
        if len(iniString) == len(set(iniString)):
            return True
         else:
            return False

原串翻转

请实现一个算法，在不使用额外数据结构和储存空间的情况下，翻转一个给定的字符串(可以使用单个过程变量)。
给定一个string iniString，请返回一个string，为翻转后的字符串。保证字符串的长度小于等于5000。

测试样例：
"This is nowcoder"
返回："redocwon si sihT"

解题思路

直接利用序列操作符切片来进行反向索引

# -*- coding:utf-8 -*-
class Reverse:
    def reverseString(self, iniString):
        return iniString[::-1]

替换空格

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

解题思路

# -*- coding:utf-8 -*-
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        return s.replace(' ','%20')

两串旋转

如果对于一个字符串A，将A的前面任意一部分挪到后边去形成的字符串称为A的旋转词。比如A="12345",A的旋转词有"12345","23451","34512","45123"和"51234"。对于两个字符串A和B，请判断A和B是否互为旋转词。
给定两个字符串A和B及他们的长度lena，lenb，请返回一个bool值，代表他们是否互为旋转词。

测试样例： "cdab",4,"abcd",4
返回：true

解题思路

# -*- coding:utf-8 -*-
class Rotation:
    def chkRotation(self, A, lena, B, lenb):
        if lena != lenb:
            return False
        return B in A+A

确定两串乱序同构

给定两个字符串，请编写程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。这里规定大小写为不同字符，且考虑字符串重点空格。
给定一个string stringA和一个string stringB，请返回一个bool，代表两串是否重新排列后可相同。保证两串的长度都小于等于5000。
测试样例：

"This is nowcoder","is This nowcoder"
返回：true "Here you are","Are you
here"
返回：false

解题思路

# -*- coding:utf-8 -*-
class Same:
    def checkSam(self, stringA, stringB):
        # write code here
        lenA = len(stringA)
        lenB = len(stringB)
        if lenA > 5000 or lenB > 5000:
            return False

        if lenA != lenB:
            return False
        result = {}
        for i in range(lenA):
            if result.has_key(stringA[i]):
                result[stringA[i]] += 1
            else:
                result[stringA[i]] = 1
            if result.has_key(stringB[i]):
                result[stringB[i]] -= 1
            else:
                result[stringB[i]] = -1

        for i in result.values():
            if i != 0:
                return False
        return True

基本字符串压缩

利用字符重复出现的次数，编写一个方法，实现基本的字符串压缩功能。比如，字符串“aabcccccaaa”经压缩会变成“a2b1c5a3”。若压缩后的字符串没有变短，则返回原先的字符串。
给定一个string iniString为待压缩的串(长度小于等于10000)，保证串内字符均由大小写英文字母组成，返回一个string，为所求的压缩后或未变化的串。

测试样例
"aabcccccaaa"
返回："a2b1c5a3"
"welcometonowcoderrrrr"
返回："welcometonowcoderrrrr"

解决思路

# -*- coding:utf-8 -*-
class Zipper:
    def zipString(self, iniString):
        # write code here
        result = iniString[0]
        count = 1
        if len(iniString)<=0:
            return iniString
        for i in range(1,len(iniString)):
            if iniString[i]==iniString[i-1]:
                count+=1
            else:
                result+=str(count)
                result+=iniString[i]
                count = 1
        result+=str(count)
        if len(result)>=len(iniString):
            return iniString
        else:
            return result

参考链接:牛客网

打赏作者