Leetcode 1417. Reformat The String

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Reformat The String

2. Solution

解析:Version 1,先分离数字和字母,如果二者数量差的绝对值大于1,则不可能形成字母数字字符串,否则,根据数量多少,按顺序依次连接字符数字数组即可。

  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
def reformat(self, s: str) -> str:
letters = []
digits = []
for ch in s:
if ch.isalpha():
letters.append(ch)
else:
digits.append(ch)
diff = len(letters) - len(digits)
if abs(diff) > 1:
return ''
elif diff == 0 or diff == 1:
arr1 = letters
arr2 = digits
else:
arr1 = digits
arr2 = letters
result = [0] * len(s)
for i in range(len(arr1)):
result[i * 2] = arr1[i]
for i in range(len(arr2)):
result[i * 2 + 1] = arr2[i]
return ''.join(result)

解析:Version 2,进一步优化。

  • Version 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
def reformat(self, s: str) -> str:
letters = 0
digits = 0
for ch in s:
if ch.isalpha():
letters += 1
else:
digits += 1
diff = letters - digits
if abs(diff) > 1:
return ''
elif diff == 0 or diff == 1:
i = 0
j = 1
else:
i = 1
j = 0
result = [0] * len(s)
for ch in s:
if ch.isalpha():
result[i] = ch
i += 2
else:
result[j] = ch
j += 2
return ''.join(result)

解析:Version 2,使用双指针,分别从两端找起,如果碰到字母和数字不符合当前位置,则交换二者。

  • Version 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
def reformat(self, s: str) -> str:
letters = 0
digits = 0
for ch in s:
if ch.isalpha():
letters += 1
else:
digits += 1
diff = letters - digits
if abs(diff) > 1:
return ''
elif diff == 0 or diff == 1:
i = 0
j = len(s) - 2
else:
i = 1
j = len(s) - 1
result = list(s)
while i < len(s) and j >=0:
while i < len(s) and result[i].isalpha():
i += 2
while j >=0 and result[j].isdigit():
j -= 2
if i < len(s) and j >=0:
result[i], result[j] = result[j], result[i]
return ''.join(result)

Reference

  1. https://leetcode.com/problems/reformat-the-string/
如果有收获,可以请我喝杯咖啡!