leetcode-482 License Key Formatting

482. License Key Formatting

Description

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:

1
2
3
4
5
6
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:

1
2
3
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:

  1. The length of string S will not exceed 12,000, and K is a positive integer.

  2. String S consists only of alphanumerical characters (a-z and/or A-Z and/or 0-9) and dashes(-).

  3. String S is non-empty.

Analyse

序列号格式化，将所有字母变为大写，以K个字母为一组，每组之间以-连接，第一组可以少于K个字母

如

Input: S = “2-5g-3-J”, K = 2

->

Output: “2-5G-3J”

看起来很简单，我写出了下面的代码，逆序遍历输入S，逐个变为大写后插入新的字符串中，每插入K个字母就追加插入一个-

看起来一切正常，然后LeetCode测试的时候输入了一个长度为44153的字符串作为输入S，k=1，爆出Memory Limit Exceeded了，这里我觉得问题出现在字符串的拼接上，每一次result = "-" + 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
char toupper(char c) {
    return ('a' <= c && c <= 'z') ? c^0x20 : c;
}

string licenseKeyFormatting(string S, int K)
{
    string result;
    int tmp = 0;
    for(int i = S.length() - 1; i >= 0; i--)
    {
        if (S[i] == '-') continue;

        if (tmp++ == K)
        {
            result = "-" + result; // 问题应该来源于这里
            tmp = 1;
        }

        result = toupper(S[i]) + result;

        cout << tmp << " : " << result << endl;
    }

    return result;
}

新的思路是直接修改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
32
33
34
35
36
37
38
39
40
char toupper(char c) {
    return ('a' <= c && c <= 'z') ? c^0x20 : c;
}

string licenseKeyFormatting(string S, int K) {
    int len = 0;
    int s_len = S.size();
    int *tag = new int[s_len]{0}; // 记录S中有字母或数字的位置

    for (int i = 0; i < s_len; i++)
    {
        if (S[i] == '-')
            continue;

        S[i] = toupper(S[i]);
        len++;
        tag[i] = 1;
    }

    len += (len - 1) / K;   // 计算最终结果的长度
    string result(len, '-');
    int pivot = len - 1;
    int tmp = 0;

    for (int j = s_len - 1; j >= 0; j--)
    {
        if (tag[j] == 1)
        {
            if (tmp++ == K)
            {
                pivot--;
                tmp = 1;
            }

            result[pivot--] = S[j];
        }
    }

    return result;
}
1
2
3
Runtime: 8 ms, faster than 97.11% of C++ online submissions for License Key Formatting.

Memory Usage: 10.9 MB, less than 34.48% of C++ online submissions for License Key Formatting.