344. 反转字符串
- 思路
- example
-
双指针, --><--
- left, right, = 0, n-1
- 终止条件：left == right
- 复杂度. 时间：O(n), 空间: O(1)
class Solution:
def reverseString(self, s: List[str]) -> None:
n = len(s)
left, right = 0, n-1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
541. 反转字符串 II
- 思路
- example
- 先转化s为list of char. (python中string 是immutable的）
- 双指针，--><--
- 复杂度. 时间：O(n), 空间: O(n)
遍历，控制步长
for i in range(0, len(s), 2*k):
class Solution:
def reverseStr(self, s: str, k: int) -> str:
def reverse(s1, left, right):
while left < right:
s1[left], s1[right] = s1[right], s1[left]
left += 1
right -= 1
s1 = list(s)
n = len(s)
for i in range(0, n, 2*k):
reverse(s1, i, min(i+k-1, n-1))
return ''.join(s1)
Offer 05. 替换空格
- 思路
- example
- 建立结果list, 遍历，join
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def replaceSpace(self, s: str) -> str:
res = []
for ch in s:
if ch == ' ':
res.append('%20')
else:
res.append(ch)
return ''.join(res)
- 双指针，倒序，<--<--
class Solution:
def replaceSpace(self, s: str) -> str:
n = len(s)
cnt = 0
for ch in s:
if ch == ' ':
cnt += 1
s1 = ['' for _ in range(n+2*cnt)]
j = n + 2*cnt - 1
for i in range(n-1, -1, -1):
if s[i] != ' ':
s1[j] = s[i]
j -= 1
else:
s1[j-2:j+1] = '%20'
j -= 3
return ''.join(s1)
class Solution:
def replaceSpace(self, s: str) -> str:
n = len(s)
cnt = 0
for ch in s:
if ch == ' ':
cnt += 1
s1 = [' ' for _ in range(n+2*cnt)]
j = n + 2*cnt -1
for i in range(n-1, -1, -1):
if s[i] != ' ':
s1[j] = s[i]
j -= 1
else:
s1[j] = '0'
s1[j-1] = '2'
s1[j-2] = '%'
j -= 3
return ''.join(s1)
151. 反转字符串中的单词
- 思路
- example
- 内置函数
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def reverseWords(self, s: str) -> str:
return ' '.join(reversed(s.split()))
- 反转两次 （局部，整体）
- step 1: trim spaces
- " abc def " --> “abc def"
- step 2: reverse each word in the string
- "cba fed"
- step 3: reverse the whole string
- “def abc"
- 细节比较多
class Solution:
def reverseWords(self, s: str) -> str:
def trim(s):
n = len(s)
left = 0
while left < n and s[left] == ' ':
left += 1
right = n-1
while left <= right and s[right] == ' ':
right -= 1
s1 = []
while left <= right:
if s[left] != ' ' or s1[-1] != ' ': # !!!
s1.append(s[left])
left += 1
return s1
def reverse_word(s1):
n = len(s1)
left, right = 0, 0
while right < n:
ch = s1[right]
if ch == ' ':
reverse(s1, left, right-1)
left = right + 1
elif right == n-1: # !!!
reverse(s1, left, right)
right += 1
def reverse(s1, left, right):
while left < right:
s1[left], s1[right] = s1[right], s1[left]
left += 1
right -= 1
# step 1, trim spaces
s1 = trim(s) # output is a list
# step 2
reverse_word(s1) # reverse each word
# step 3
reverse(s1, 0, len(s1)-1) # reverse the whole list
return ''.join(s1)
class Solution:
def reverseWords(self, s: str) -> str:
def trim(s):
n = len(s)
left, right = 0, n-1
while left <= right and s[left] == ' ':
left += 1
while left <= right and s[right] == ' ':
right -= 1
s1 = []
while left <= right:
if s[left] != ' ' or s1[-1] != ' ':
s1.append(s[left])
left += 1
return s1
def reverse(s1, left, right):
while left < right:
s1[left], s1[right] = s1[right], s1[left]
left += 1
right -= 1
def reverse_word(s1):
i = 0
for j in range(1, len(s1)-1):
if s1[j] == ' ':
reverse(s1, i, j-1)
i = j + 1
reverse(s1, i, len(s1)-1)
s1 = trim(s)
reverse_word(s1)
reverse(s1, 0, len(s1)-1)
return ''.join(s1)
Offer 58 II. 左旋转字符串
- 思路
- example
- 切片
- "abcde", "de" + "abc" (k=3)
- 复杂度. 时间：O(N), 空间: O(N)
class Solution:
def reverseLeftWords(self, s: str, n: int) -> str:
return s[n:] + s[:n]
- 字符串拼接
class Solution:
def reverseLeftWords(self, s: str, n: int) -> str:
res = ''
for i in range(n, len(s)):
res += s[i]
for i in range(n):
res += s[i]
return res
- 两部分各自反转，最后整串反转 (局部反转，再整体反转）
- 需要转化为list
class Solution:
def reverseLeftWords(self, s: str, n: int) -> str:
def reverse(s, left, right):
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
s1 = list(s)
reverse(s1, 0, n-1)
reverse(s1, n, len(s)-1)
reverse(s1, 0, len(s)-1)
return ''.join(s1)
class Solution:
def reverseLeftWords(self, s: str, n: int) -> str:
def reverse(s1, left, right):
while left < right:
s1[left], s1[right] = s1[right], s1[left]
left += 1
right -= 1
N = len(s)
s1 = list(s)
reverse(s1, 0, n%N-1)
reverse(s1, n%N, N-1)
reverse(s1, 0, N-1)
return ''.join(s1)
class Solution:
def reverseLeftWords(self, s: str, n: int) -> str:
def reverse(s1, left, right):
while left < right:
s1[left], s1[right] = s1[right], s1[left]
left += 1
right -= 1
s1 = list(s)
reverse(s1, 0, n-1)
reverse(s1, n, len(s1)-1)
reverse(s1, 0, len(s1)-1)
return ''.join(s1)
