字符串编码、反转与回文
实现单词原地反转、游程编码和回文检测，包括向中心扩展的技巧。
字符串编码、反转与回文 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
原地反转字符串
Python 字符串不可变，因此“原地”反转意味着先将其转换为字符列表，再使用双指针交换字符，最后使用 join 拼接。经典的双指针交换方法是：将 left 放在索引 0，将 right 放在最后一个索引；交换字符并让两个指针向内移动，直到它们相遇或交叉。字符列表需要 O(n) 时间和 O(n) 空间（由于字符串不可变，这是无法避免的）。
def reverse_string(s):
chars = list(s)
left, right = 0, len(chars) - 1
while left < right:
chars[left], chars[right] = chars[right], chars[left]
left += 1
right -= 1
return ''.join(chars)
print(reverse_string('hello')) # 'olleh'
print(reverse_string('Hannah')) # 'hannaH'
# Pythonic shortcut (creates new string):
print('hello'[::-1]) # 'olleh'反转句子中的单词
请反转单词的顺序，同时去除多余空格。简洁的 Python 解法是：使用 split（可处理多个空格），反转列表，再使用 join。对字符数组进行原地反转时：先使用 reverse 反转整个数组，再反转每个单独的单词。这种双遍方法的时间复杂度为 O(n)，空间复杂度为 O(n)（由于 Python 字符串不可变，这是无法避免的）。
def reverse_words(s):
words = s.split() # split and strip whitespace
words.reverse() # in-place reverse
return ' '.join(words) # single space between words
print(reverse_words(' hello world ')) # 'world hello'
print(reverse_words('a good example')) # 'example good a'
# One-liner:
print(' '.join(' hello world '.split()[::-1]))回文检测：简单方法
如果一个字符串等于其 reverse，它就是回文。最快的 Python 检查方式是：s == s[::-1]。对于不区分大小写且仅包含字母数字字符的回文（面试中最常见的变体），请先规范化字符串：过滤非字母数字字符并转换为小写，然后进行比较。这两种方法的时间复杂度都是 O(n)。
def is_palindrome(s):
# Filter and normalise
cleaned = ''.join(c.lower() for c in s if c.isalnum())
return cleaned == cleaned[::-1]
print(is_palindrome('A man, a plan, a canal: Panama')) # True
print(is_palindrome('race a car')) # False
print(is_palindrome('Was it a car or a cat I saw?')) # True回文检测：双指针
如果希望将额外空间降至 O(1)，请使用双指针而不是切片来检查回文。将 left 放在 0，将 right 放在末尾。跳过非字母数字字符，以不区分大小写的方式比较其余字符，并在不匹配时返回假值。这种方法虽然更加冗长，但完全避免了创建清理后的字符串——当内存受限时，这一点非常重要。
def is_palindrome_twoptr(s):
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1; right -= 1
return True
print(is_palindrome_twoptr('A man, a plan, a canal: Panama')) # True围绕中心扩展查找最长回文
围绕中心扩展技术可以在 O(n²) 时间和 O(1) 额外空间内找到最长回文子串。对于每个字符（奇数长度回文）以及字符之间的每个间隙（偶数长度回文），在字符匹配时向外 expand。请记录遇到的最佳（start，end）区间。共有 2n-1 个中心，每次扩展在最坏情况下需要 O(n) 时间。
def longest_palindrome(s):
best_start = best_end = 0
def expand(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1; right += 1
return left + 1, right - 1 # last valid bounds
for i in range(len(s)):
l, r = expand(i, i) # odd-length
if r - l > best_end - best_start:
best_start, best_end = l, r
l, r = expand(i, i + 1) # even-length
if r - l > best_end - best_start:
best_start, best_end = l, r
return s[best_start:best_end+1]
print(longest_palindrome('babad')) # 'bab' or 'aba'
print(longest_palindrome('cbbd')) # 'bb'Manacher 算法预览
Manacher 算法利用这样的规律，在一个更大的回文内部的回文可以根据其镜像位置进行初始化，从而在 O(n) 时间内找到最长回文子串。面试中很少要求实现它，但了解它的存在仍然很有价值。大多数面试官都会接受 O(n²) 的围绕中心扩展方法，认为它“已经足够优化”——如果面试官要求进一步改进，请提及 Manacher 算法这一理论上的 O(n) 解法。
# Manacher's: O(n) longest palindromic substring
def manacher(s):
# Transform s into '#a#b#a#' to handle even/odd uniformly
t = '#' + '#'.join(s) + '#'
n = len(t)
P = [0] * n # P[i] = palindrome radius at i
center = right = 0
for i in range(n):
mirror = 2 * center - i
if i < right:
P[i] = min(right - i, P[mirror])
while (i + P[i] + 1 < n and i - P[i] - 1 >= 0
and t[i+P[i]+1] == t[i-P[i]-1]):
P[i] += 1
if i + P[i] > right:
center, right = i, i + P[i]
max_len = max(P)
center_idx = P.index(max_len)
start = (center_idx - max_len) // 2
return s[start:start+max_len]
print(manacher('babad')) # 'bab'游程编码
游程编码（RLE）会压缩连续重复的字符：'aaabbc' 会变成 'a3b2c1'。实现时，请使用快指针扫描，以找到每个游程的末尾；将字符和计数写入输出列表，然后使用 join。对于较短的游程，输入可能比编码后的输出更短——返回编码结果前，请始终检查编码版本是否更短。
def encode_rle(s):
if not s: return ''
parts = []
i = 0
while i < len(s):
char = s[i]
j = i
while j < len(s) and s[j] == char:
j += 1
count = j - i
parts.append(char + (str(count) if count > 1 else ''))
i = j
encoded = ''.join(parts)
return encoded if len(encoded) < len(s) else s
print(encode_rle('aaabbc')) # 'a3b2c'
print(encode_rle('abc')) # 'abc' (no compression gain)解码游程编码字符串
RLE 解码会读取字符及其后面的数字序列，并展开每个游程。面试官有时会给出 LeetCode 变体，其中使用 k[encoded_string] 表示重复的子字符串，例如 3[ab] → ababab。这种嵌套变体需要使用栈来处理多层嵌套。
def decode_rle(s):
result = []
i = 0
while i < len(s):
char = s[i]; i += 1
num_str = ''
while i < len(s) and s[i].isdigit():
num_str += s[i]; i += 1
count = int(num_str) if num_str else 1
result.append(char * count)
return ''.join(result)
print(decode_rle('a3b2c')) # 'aaabbc'
print(decode_rle('a2b3c1')) # 'aabbbc'
# Nested bracket decode (LeetCode 394)
def decode_bracket(s):
stack = []
for c in s:
if c != ']':
stack.append(c)
else:
chars = []
while stack[-1] != '[':
chars.append(stack.pop())
stack.pop() # remove '['
k = int(stack.pop())
stack.append(''.join(reversed(chars)) * k)
return ''.join(stack)
print(decode_bracket('3[ab]')) # 'ababab'有效回文 II：允许删除一个字符
给定一个字符串，如果最多删除一个字符后可以将其变成回文，则返回真值。请使用双指针；在首次不匹配时，检查 s[left+1:right+1] 或 s[left:right] 是否为回文（也就是尝试跳过两个不匹配字符中的每一个）。如果任一部分是回文，则返回真值。该贪心方法有效，因为跳过不匹配字符是唯一有用的操作。
def valid_palindrome(s):
def is_pal(l, r):
while l < r:
if s[l] != s[r]: return False
l += 1; r -= 1
return True
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
# Try skipping either character
return is_pal(left+1, right) or is_pal(left, right-1)
left += 1; right -= 1
return True
print(valid_palindrome('aba')) # True
print(valid_palindrome('abca')) # True (delete 'c')
print(valid_palindrome('abc')) # False回文分割 I
请将字符串分割为所有由回文组成的子串。使用回溯：每一步都尝试剩余字符串的所有前缀；如果某个前缀是回文，就对剩余部分递归处理。请使用区间 DP 预先计算二维布尔表 is_pal[i][j]，使回文检查的时间复杂度降为 O(1)，从而将整体回溯复杂度从 O(n² × 2^n) 降至 O(n × 2^n)——由于生成所有分割方案本质上是指数级的，这样的复杂度是可以接受的。
def partition(s):
n = len(s)
dp = [[False]*n for _ in range(n)]
for i in range(n):
dp[i][i] = True
for length in range(2, n+1):
for i in range(n-length+1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = length == 2 or dp[i+1][j-1]
result = []
def backtrack(start, path):
if start == n: result.append(path[:]); return
for end in range(start, n):
if dp[start][end]:
path.append(s[start:end+1])
backtrack(end+1, path)
path.pop()
backtrack(0, [])
return result
print(partition('aab')) # [['a','a','b'],['aa','b']]最短回文：字符串哈希
请找出通过在字符串前面添加字符所能得到的最短回文。关键思路是：找到 s 的最长回文前缀，然后将剩余后缀的 reverse 添加到前面。为了高效找到最长回文前缀，请在字符串 s + '#' + reverse(s) 上使用 KMP 的失配函数。失配函数的最后一个值就是最长回文前缀的长度。
def shortest_palindrome(s):
rev = s[::-1]
combined = s + '#' + rev # '#' prevents overlap
n = len(combined)
kmp = [0] * n
j = 0
for i in range(1, n):
while j > 0 and combined[i] != combined[j]:
j = kmp[j-1]
if combined[i] == combined[j]:
j += 1
kmp[i] = j
# kmp[-1] = length of longest palindromic prefix
to_add = rev[:len(s) - kmp[-1]]
return to_add + s
print(shortest_palindrome('aacecaaa')) # 'aaacecaaa'
print(shortest_palindrome('abcd')) # 'dcbabcd'快速检查
请检验您对本课中数据结构与算法——编程面试准备相关概念的理解。
课程回顾
本课中，您学习了：使用双指针检测回文的时间复杂度为 O(n)、空间复杂度为 O(1)——当空间重要时，应始终优先使用基于索引的检查，而不是分配一个反转后的 copy，围绕中心扩展将 2n-1 个位置中的每一个视为潜在回文中心，从而在 O(n²) 时间内找到最长回文子串，以及游程编码在 O(n) 时间内压缩连续游程，而解码嵌套括号变体时需要使用栈。接下来我们将学习冒泡排序和插入排序。
常见问题解答
「字符串编码、反转与回文」课时是免费的吗？
是的 — 「字符串编码、反转与回文」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「字符串编码、反转与回文」这节课中我会学到什么？
实现单词原地反转、游程编码和回文检测，包括向中心扩展的技巧。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「字符串编码、反转与回文」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 面试必备的 Python 字符串 API
- 子串的滑动窗口
- 字母异位词与字符频率映射
- 字符串编码、反转与回文