【EASY】License Key Formatting

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

问题

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 就分段即可。

解决方法

using namespace std;

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

int main(int argc, const char * argv[]) {
    
    {
        string str = "5F3Z-2e-9-w";
        int k = 4;
        string result = formateLicense(str, k);
        cout << result << endl;
    }
    
    {
        string str = "2-5g-3-J";
        int k = 2;
        string result = formateLicense(str, k);
        cout << result << endl;
    }
    
    {
        string str = "AAAAAA";
        int k = 1;
        string result = formateLicense(str, k);
        cout << result << endl;
    }
    
    {
        string str = "----";
        int k = 2;
        string result = formateLicense(str, k);
        cout << result << endl;
    }
    return 0;
}

Thanks for reading.

All the best wishes for you! 💕