字符串匹配 ：又称 「模式匹配」。可以简单理解为，给定字符串 T 和 p，在主串 T 中寻找子串 p。主 串 T 又被称为 「文本串」 ，子串 p 又被称为 「模式串」 。在字符串问题中，最重要的问题之一就是字符串匹配问题。而按照模式串的个数，可以将字符串匹 配问题分为：「单模式串匹配问题」和「多模式串匹配问题
def bruthForce(T:str, p:str) -> str:
n, m = len(T), len(p)
i, j = 0, 0
while i < n and j < m:
if p[j] == T[i]:
i += 1
j += 1
else:
i = i-(j-1) # 匹配失败，i移动到上次匹配开始位置的下一个位置
j = 0
if j == m: # 匹配成功，返回匹配的开始位置
return i-j
return -1 # 匹配失败，返回-1
# 生成next数组
# next[j]表示下标j之前的模式串p中，最长相等前后缀的长度
def generateNext(p: str):
m = len(p)
next = [0 for _ in range(m)] # 初始化数组元素全部为0
left = 0 # left表示前缀串开始所在的下标位置
for right in range(1, m): # right表示后缀串开始所在的下标位置
while left > 0 and p[left] != p[right]: # 匹配不成功，left进行回退，left==0时停止回退
left = next[left-1] # left进行回退操作
if p[left] == p[right]: # 匹配成功，找到相同的前后缀，先让left+=1， 此时left为前缀长度
left += 1
next[right] = left # 记录前缀长度，更新next[right]， 结束本次循环，right+=1
return next
# KMP 匹配算法，T为文本串，p为模式串
def kmp(T:str, p:str) -> int:
n = len(T)
m = len(p)
next = generateNext(p) # 生成next数组
j = 0 # j为模式串中当前匹配的位置
for i in range(n): # i 为文本串中当前匹配的位置
while j > 0 and T[i] != p[j]: # 如果模式串前缀匹配不成功，将模式串进行回退，j==0时候停止回退
j = next[j-1]
if T[i] == p[j]: # 当前模式串前缀匹配成功，令j+=1,继续匹配
j += 1
if j == m: # 当前模式串完全匹配成功，返回匹配开始位置
return i-j+1
return -1 # 匹配失败，返回-1
class Solution:
def isPalindrome(self, s: str) -> bool:
if not s or len(s) < 1:
return False
length = len(s)
if length == 1:
return True
left = 0
right = length-1
while left < right:
if not s[left].isalnum():
left += 1
continue
if not s[right].isalnum():
right -= 1
continue
if s[left].lower() == s[right].lower():
left += 1
right -= 1
else:
return False
return True
C++实现
代码语言：javascript
复制
class Solution {
public:
bool isPalindrome(string s) {
string sgood;
for(char ch:s)
{
if(isalnum(ch))
{
sgood += tolower(ch);
}
}
int n = sgood.size();
int left = 0;
int right = n-1;
while(left < right)
{
if (sgood[left] != sgood[right])
{
return false;
}
++left;
--right;
}
return true;
}
};
127 翻转字符串里的单词
题目大意：描述：给定一个字符串 s。要求：逐个翻转字符串中所有的单词。注意：
数组字符串 s 可以再前面、后面或者单词间包含多余的空格
翻转后的单词应当只有一个空格分隔
翻转后的字符串不应该包含额外的空格
示例 ：
代码语言：javascript
复制
输入：s = "the sky is blue"
输出："blue is sky the"
代码语言：javascript
复制
输入：s = " hello world "
输出："world hello"
解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。
代码语言：javascript
复制
输入：s = "a good example"
输出："example good a"
解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。
代码语言：javascript
复制
输入：s = " Bob Loves Alice "
输出："Alice Loves Bob"
代码语言：javascript
复制
输入：s = "Alice does not even like bob"
输出："bob like even not does Alice"
class Solution:
def reverseWords(self, s: str) -> str:
ss = s.split()
return ' '.join(ss[::-1])
或者
代码语言：javascript
复制
class Solution:
def reverseWords(self, s: str) -> str:
words = []
cur == ''
for ch in s:
if ch == ' ':
if cur:
words.append(cur)
cur = ''
else:
cur += ch
if cur:
words.append(cur)
return ' '.join(words[::-1])
自己实现
fig
代码语言：javascript
复制
class Solution:
def trim_spaces(self, s: str) -> list:
left, right = 0, len(s) - 1
# 去掉字符串开头的空白字符
while left <= right and s[left] == ' ':
left += 1
# 去掉字符串末尾的空白字符
while left <= right and s[right] == ' ':
right -= 1
# 将字符串间多余的空白字符去除
output = []
while left <= right:
if s[left] != ' ':
output.append(s[left])
elif output[-1] != ' ':
output.append(s[left])
left += 1
return output
def reverse(self, l: list, left: int, right: int) -> None:
while left < right:
l[left], l[right] = l[right], l[left]
left, right = left + 1, right - 1
def reverse_each_word(self, l: list) -> None:
n = len(l)
start = end = 0
while start < n:
# 循环至单词的末尾
while end < n and l[end] != ' ':
end += 1
# 翻转单词
self.reverse(l, start, end - 1)
# 更新start，去找下一个单词
start = end + 1
end += 1
def reverseWords(self, s: str) -> str:
l = self.trim_spaces(s)
# 翻转字符串
self.reverse(l, 0, len(l) - 1)
# 翻转每个单词
self.reverse_each_word(l)
return ''.join(l)
C++实现
代码语言：javascript
复制
class Solution {
public:
string reverseWords(string s) {
// 反转整个字符串
reverse(s.begin(), s.end());
int n = s.size();
int idx = 0;
for (int start = 0; start < n; ++start) {
if (s[start] != ' ') {
// 填一个空白字符然后将idx移动到下一个单词的开头位置
if (idx != 0) s[idx++] = ' ';
// 循环遍历至单词的末尾
int end = start;
while (end < n && s[end] != ' ') s[idx++] = s[end++];
// 反转整个单词
reverse(s.begin() + idx - (end - start), s.begin() + idx);
// 更新start，去找下一个单词
start = end;
}
}
s.erase(s.begin() + idx, s.end());
return s;
}
};
在允许最多删除一个字符的情况下，同样可以使用双指针，通过贪心实现。初始化两个指针 low 和 high 分别指向字符串的第一个字符和最后一个字符。每次判断两个指针指向的字符是否相同，如果相同，则更新指针，将 low 加 1，high 减 1，然后判断更新后的指针范围内的子串是否是回文字符串。如果两个指针指向的字符不同，则两个字符中必须有一个被删除，此时就分成两种情况：即删除左指针对应的字符，留下子串
s[low+1:high]
，或者删除右指针对应的字符，留下子串
s[low:high−1]
。当这两个子串中至少有一个是回文串时，就说明原始字符串删除一个字符之后就以成为回文串。
fig1
python实现
代码语言：javascript
复制
class Solution:
def validPalindrome(self, s: str) -> bool:
length = len(s)
if not str or length < 1:
return False
if length == 1:
return True
left = 0
right = length-1
while left < right:
if s[left] == s[right]:
left += 1
right -= 1
else:
return self.isPalindrome(s, left+1, right) or self.isPalindrome(s, left, right-1) # 递归
return True
def isPalindrome(self, s:str, left, right) -> bool:
while left < right:
if s[left] == s[right]:
left += 1
right -= 1
else:
return False
return True
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 ：
代码语言：javascript
复制
输入：s = "3[a]2[bc]"
输出："aaabcbc"
代码语言：javascript
复制
输入：s = "3[a2[c]]"
输出："accaccacc"
代码语言：javascript
复制
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
代码语言：javascript
复制
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"
1 <= s.length <= 30
``s由小写英文字母、数字和方括号'[]'` 组成
s 保证是一个 有效 的输入。
s 中所有整数的取值范围为 [1, 300]
解题思路：
由于存在括号, 所以使用栈来保存后进先出的原则;
栈内需要保存的是括号前的数字k, 以及括号前已经组成的字符串res;
遇到括号闭合时, 则将字符串按规则进行拼接；
python实现
代码语言：javascript
复制
class Solution:
def decodeString(self, s: str) -> str:
stack = []
for ch in s:
if ch != ']':
stack.append(ch)
else:
tmp = []
num = ''
# 先找要重复的子字符串
while stack[-1] != '[' and not stack[-1].isdigit():
tmp.append(stack.pop())
tmp = ''.join(tmp[::-1]) # 反序拼接
# 移除'['
stack.pop()
# 再找重复的次数（数字）
while stack and stack[-1].isdigit():
num += stack.pop()
num = num[::-1]
num = int(num) if num else num
# 重复子字符串，并加入到stack中
# print(tmp, num)
if num:
stack.append(tmp*num)
# print(ch, stack)
return ''.join(stack)
