目录
字符串相关概念：
回文
子串
子序列
前缀树
后缀树和后缀数组
匹配
字典序
字符串操作：
1.与数组相关的操作 增删改查
2.字符的替换
3.字符串的旋转
字符串题目的常见类型
1.规则判断
- 判断字符串是否符合整数规则
- 判断字符串是否符合浮点数规则
- 判断字符串是否符合会问字符串规则
2.数字运算
int 和long 类型表达整数范围有限所以经常用字符串实现大整数
与大整数相关的加减乘除操作，需要模拟笔算的过程
3.与数组操作相关的类型
- 数组相关的调整、排序等操作需要掌握
- 快速排序的划分过程需要掌握和改写
4.字符计数
- hash表
- 固定长度的数组
- 滑动串口问题、寻找无重复字符子串问题、计算变位词问题
5.动态规划类型
- 最长公共子串
- 最长公共子串序列
- 最长回文子串
- 最长回文子序列
6.搜索类型
- 宽度优先搜索
深度优先搜索
7.高级算法与数据结构
- manacher算法解决最长回文子串问题
kmp算法解决字符串匹配问题
前缀树结构
后缀树和后缀数组
对于两棵彼此独立的二叉树A和B，请编写一个高效算法，检查A中是否存在一棵子树与B树的拓扑结构完全相同。给定两棵二叉树的头结点A和B，请返回一个bool值，代表A中是否存在一棵同构于B的子树。
解决办法：
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class IdenticalTree:
def bianli(self,A):
if A==None:
return '#'
string=str(A.val)
string+=self.bianli(A.left)
string+=self.bianli(A.right)
return string
def chkIdentical(self, A, B):
astr=self.bianli(A)
bstr=self.bianli(B)
if bstr in astr:
return True
else:
return False
给定两个字符串A和B及他们的长度，请返回一个bool值，代表他们是否互为变形词。
对于两个字符串A和B，如果A和B中出现的字符种类相同且每种字符出现的次数相同，则A和B互为变形词，请设计一个高效算法，检查两给定串是否互为变形词。
测试样例：
"abc",3,"bca",3
返回：true
解决方法：
class Transform:
def chkTransform(self, A, lena, B, lenb):
# write code here
if lena != lenb:
return False
hashTable = [0 for i in xrange(0,256)]
for x in A:
hashTable[ord(x)] += 1
for x in B:
hashTable[ord(x)] -= 1
if not max(hashTable):
return True
else:
return False
旋转词判断
如果一个字符串str,把字符串str前面任意的部分挪到后面去形成的字符串叫做str的旋转词，比如str= "1234",str的旋转词有 “1234” “2341” “3412” "4123".给定两个字符串a 和 b ,请判断a 和 b 是否互为旋转词。
举例：
a = "dcab" , b = "abcd",返回 true
a = "1ab2", b = "ab12",返回 false
解决思路：
1.先判断str1 与 str2 是否相等
2.如果长度相等，生成str1+ str1 的大字符串
3.用KMP算法判断大字符串中是否含有str2
时间复杂度为O(n)
如“1234” 生成大字符串 “12341234” ，其中包括“1234”所有的旋转词
解决方法：
# -*- coding:utf-8 -*-
class Rotation:
def chkRotation(self, A, lena, B, lenb):
if lena != lenb:
return False
return B in A+A
给定字符串str，做单词间逆序调整
举例：
“pig loves dog ” 逆序成 “dog loves pig”
解决思路：
1.实现将字符串局部所有字符逆序的函数f
“pig love dog ->"gip evols god"
2.利用f将字符串所有字符逆序
“gip evols god” ->"god sevol gip"
3.找到逆序后的字符串中每一个单词的区域，利用f将每一个单词的区域逆序
"god sevol gip" ->"dog loves pig"
解决方法：
# -*- coding:utf-8 -*-
class Reverse:
def reverseSentence(self, A, n):
A = A.split()
return ' '.join(A[::-1])
给定一个字符串str,和一个整数i,i代表str中的位置，将str[0..i]移到右侧，str[i+1..N-1]移到左侧
举例：
str = "ABCDE" ,i = 2,将str调整为“DEABC”
要求时间复杂度为O(N),额外空间复杂度为O(1)
解决思路：
1.将str[0..i]部分的字符逆序
2.将str[i+1..N-1]部分的字符逆序
3.将str整体的字符逆序
解决方法：
# -*- coding:utf-8 -*-
class Translation:
def stringTranslation(self, A, n, len):
# write code here
str1 = A[:len]
str2 = A[len:]
A = str1[::-1] + str2[::-1]
return A[::-1]
字符交换相关题目大部分是活用局部逆序函数的组合
对于一个给定的字符串数组，请找到一种拼接顺序，使所有小字符串拼接成的大字符串是所有可能的拼接中字典序最小的。
给定一个字符串数组strs，同时给定它的大小，请返回拼接成的串。
测试样例：
["abc","de"],2
"abcde"
解决方法：
# -*- coding:utf-8 -*-
# 如果str1 + str2 < str2 +str1 ,否则，str2放在前面
class Prior:
def findSmallest(self, strs, n):
strs.sort(lambda x, y: cmp(x + y, y + x))
return ''.join(strs)
空格替换
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
解决方法：
# -*- coding:utf-8 -*-
class Solution:
# s 源字符串
def replaceSpace(self, s):
return s.replace(' ','%20')
对于一个字符串，请设计一个算法，判断其是否为一个合法的括号串。
给定一个字符串A和它的长度n，请返回一个bool值代表它是否为一个合法的括号串。
测试样例：
"(()())",6
返回：true
测试样例：
"()a()()",7
返回：false
测试样例：
"()(()()",7
返回：false
解决方法：
# -*- coding:utf-8 -*-
class Parenthesis:
def chkParenthesis(self, A, n):
count = 0
for i in A:
if count < 0:
return False
if i == '(':
count += 1
elif i == ')':
count -= 1
else:
return False
if count == 0:
return True
else:
return False
对于一个字符串,请设计一个高效算法，找到字符串的最长无重复字符的子串长度。
给定一个字符串A及它的长度n，请返回它的最长无重复字符子串长度。保证A中字符全部为小写英文字符，且长度小于等于500。
测试样例：
"aabcb",5
返回：3
解决方法：
正想》》》》》》》》》》》
打赏作者
