題目

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:

翻譯

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

分析

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

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