題目

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:

Example 2:

Note:

翻譯

給定一個非空字符串S，代表一個軟件授權秘鑰，我們需要格式化這個秘鑰。這個字符串由字母、數字(a-z and/or A-Z and/or 0-9)和中劃線(-)組成。中劃線把字符串S分為幾個組（例如有M個中劃線，那會被分為M+1個組）。現在，中劃線放置的位置可能被放錯了。 我們希望每個組的字符長度為整數K（除了第一個組，允許少于K，但是至少要有一個字符）。為了滿足這個需求，我們需要重新放置中劃線。另外，還需要把所有小寫字母轉換為大寫字母。 提示： 1. S的長度不會超過12000，K是一個正整數。 2. S只包含字母、數字和中劃線。 3. S非空。

分析

由于給定的字符串S還無法判斷直接有效字符（除中劃線外）的個數，故先做一次遍歷。筆者在這次遍歷中，將所有有效字符全部左移了，并轉化了大小寫。 得到有效字符的個數后，就可以算出最終字符的長度newLen了，進而創建這個新字符數組。遍歷這個新數組進行填充即可。

java版代碼（時間復雜度O(n),空間復雜度O(n)）: