Leetcode 482 License Key Formatting

发表于 |

You are given a license key represented as a string S which consists only alphanumeric character and dashes. The string is separated into N+1 groups by N dashes.

Given a number K, we would want to reformat the strings such that each group contains exactly K characters, except for the first group which could be shorter than K, but still must contain at least one character. Furthermore, there must be a dash inserted between two groups and all lowercase letters should be converted to uppercase.

Given a non-empty string S and a number K, format the string according to the rules described above.

Example 1:
Input: S = “5F3Z-2e-9-w”, K = 4
Output: “5F3Z-2E9W”
Explanation: The string S has been split into two parts, each part has 4 characters.
Note that the two extra dashes are not needed and can be removed.

Example 2:
Input: S = “2-5g-3-J”, K = 2
Output: “2-5G-3J”
Explanation: The string S has been split into three parts, each part has 2 characters except the first part as it could be shorter as mentioned above.

Note:
The length of string S will not exceed 12,000, and K is a positive integer.
String S consists only of alphanumerical characters (a-z and/or A-Z and/or 0-9) and dashes(-).
String S is non-empty.

分析：

  1. 题目写得挺长，实际上是将一个字符串（由’-‘连接）重新均分成若干份，每份长度为K（第一份可不够），然后用’-‘将每份连接
  2. 注意S长度不超过12000，代表这道题可以闭着眼睛写都不会超时
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
32
33
34
35
36
37
38
39
# 借用到python里的upper()函数直接将字符串全部大写，说实话有点耍赖了
class Solution(object):
	# 弱智方法1，倒叙遍历，每遍历K个就存一下，最后连接，在出循环的时候判断一下是不是有多余的字段没存就存一下。
    def licenseKeyFormatting1(self, S, K):
        """
        :type S: str
        :type K: int
        :rtype: str
        """
        n = len(S)
        rec,res = '',[]
        for i in range(n-1,-1,-1):
            if S[i] != '-':
                rec += S[i]
                if len(rec) == K:
                    rec = rec.upper()
                    res.append(rec[::-1])
                    rec = ''
        if rec: res.append(rec.upper()[::-1])

        return '-'.join(res[::-1])

    # 好一点的方法，我直接用replace()和upper()处理字符串，然后直接连接就完事了
    # 如'5F3Z-2e-9-w' 直接变成 'W92EZ3F5'
    def licenseKeyFormatting2(self,S,K):
    	S = S.replace('-','').upper()[::-1]
    	return '-'.join([S[i:i+K][::-1] for i in range(len(S))[::K]][::-1])

Solution 1:
	O(n) time, O(n) space
	38 / 38 test cases passed.
	difficulty: easy
	Runtime: 149 ms,beats 49%

Solution 2:
	O(n) time, O(n) space
	38 / 38 test cases passed.
	difficulty: easy
	Runtime: 46 ms,beats 90%