【EASY】License Key Formatting

发布于: 2019-01-09 16:07
阅读: 59
评论: 0
喜欢: 0

问题

原题链接:https://leetcode.com/problems/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.

分析过程

  • 输入:只有数字、字母和横杠的字符串以及一个分段长度 k
  • 输出:按 k 分段格式化以后的字符串
  • 思路:由于输出的长度有可能超过输入,因此不能在原字符串修改,需要开辟临时空间。由于题目规定只有第一段长度可以小于 k,因此采取反向输入的方法,在临时空间中反向输入字符。输入时记录长度,如果到达 k 就分段即可。

解决方法

class Solution {
public:
    string licenseKeyFormatting(string S, int K) {
        // 题目已规定输入是合法的
        const char *strPtr = S.c_str();
        int len = (int)strlen(strPtr);
        // 分配临时空间
        // 题目规定输入最长12000,如果k是1,结果最长24000
        // 但是testcase里有一个长度四万的case(- -|||)
        char buff[80001];
        memset(buff, 0, 80001);
        // 从后往前输入,定义两个指针,分别指向源字符串的末尾和buffer的末尾
        const char *srcPtr = strPtr + len - 1;
        char *dstPtr = buff + 80001 - 2;
        // 字符分段计数,用于和k比较
        int kCounter = 0;
        // 循环结束条件是源字符串扫描结束或buff用完
        while (srcPtr >= strPtr && dstPtr >= buff) {
            if (kCounter >= K) {
                // 如果已经达到k,则输出-并清空计数
                *dstPtr = '-';
                kCounter = 0;
                --dstPtr;
            } else {
                // 如果没有达到计数,则输入字符
                // 首先跳过所有-
                while (srcPtr >= strPtr && dstPtr >= buff && *srcPtr == '-') {
                    --srcPtr;
                }
                // 检查是不是到循环结束条件了
                if (srcPtr < strPtr || dstPtr < buff) {
                    break;
                }
                // 输入字符并增加计数和移动指针
                char c = *srcPtr;
                *dstPtr = c >= 'a' && c <= 'z' ? c - 32 : c;
                ++kCounter;
                --srcPtr;
                --dstPtr;
            }
        }
        // 跳过开头的-
        while (*(dstPtr + 1) == '-' ) {
            dstPtr++;
        }
        // 返回结果
        return string(dstPtr + 1);
    }
};

Thanks for reading.

All the best wishes for you! 💕