[LeetCode] 482. License Key Formatting

[grandyang]

 

Now you are given a string S, which represents a software license key which we would like to format. The string S is composed of alphanumerical characters and dashes. The dashes split the alphanumerical characters within the string into groups. (i.e. if there are M dashes, the string is split into M+1 groups). The dashes in the given string are possibly misplaced.

We want each group of characters to be of length K (except for possibly the first group, which could be shorter, but still must contain at least one character). To satisfy this requirement, we will reinsert dashes. Additionally, all the lower case letters in the string must be converted to upper case.

So, you are given a non-empty string S, representing a license key to format, and an integer K. And you need to return the license key formatted according to the description above.

Example 1:

**Input:** S = "2-4A0r7-4k", K = 4

**Output:** "24A0-R74K"

**Explanation:** The string S has been split into two parts, each part has 4 characters.

Example 2:

**Input:** S = "2-4A0r7-4k", K = 3

**Output:** "24-A0R-74K"

**Explanation:** The string S has been split into three parts, each part has 3 characters except the first part as it could be shorter as said 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.

 

这道题让我们对注册码进行格式化，正确的注册码的格式是每四个字符后面跟一个短杠，每一部分的长度为K，第一部分长度可以小于K，另外，字母必须是大写的。那么由于第一部分可以不为K，那么我们可以反过来想，我们从S的尾部往前遍历，把字符加入结果res，每K个后面加一个短杠，那么最后遍历完再把res翻转一下即可，注意翻转之前要把结尾的短杠去掉(如果有的话)，参见代码如下：

 

解法一：

class Solution {
public:
    string licenseKeyFormatting(string S, int K) {
        string res = "";
        int cnt = 0, n = S.size();
        for (int i = n - 1; i >= 0; --i) {
            char c = S[i];
            if (c == '-') continue;
            if (c >= 'a' && c <= 'z') c -= 32;
            res.push_back(c);
            if (++cnt % K == 0) res.push_back('-');
        }
        if (!res.empty() && res.back() == '-') res.pop_back();
        return string(res.rbegin(), res.rend());
    }
};

 

上面代码可以进一步精简到下面这种，我们用到了自带函数toupper，把字母转为大写格式，参见代码如下：

 

解法二：

class Solution {
public:
    string licenseKeyFormatting(string S, int K) {
        string res = "";
        for (int i = (int)S.size() - 1; i >= 0; --i) {
            if (S[i] != '-') {
                ((res.size() % (K + 1) - K) ? res : res += '-') += toupper(S[i]);
            }
        }
        return string(res.rbegin(), res.rend());
    }
};

 

参考资料：

https://discuss.leetcode.com/topic/74995/java-5-lines-clean-solution

https://discuss.leetcode.com/topic/74925/short-and-fast-java-solution

https://discuss.leetcode.com/topic/74993/4-line-c-concise-solution-to-scan-string-backward

 

LeetCode All in One 题目讲解汇总(持续更新中...)