Leetcode 1417. Reformat The String

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

1. Description

2. Solution

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

• Version 1

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)
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

**解析：**Version 2，进一步优化。

• Version 2

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)
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

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

• Version 3

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)
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

Reference

1. https://leetcode.com/problems/reformat-the-string/