### 题目

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.

### 直接用String库和StringBuilder处理

#### 代码

class Solution {
public String licenseKeyFormatting(String S, int K) {
S = S.toUpperCase();
S = S.replaceAll("-","");
StringBuilder sb = new StringBuilder(S);
for (int end = sb.length(), start = end - K; start > 0; end = start, start = end - K) {
sb.insert(start, '-');
}
return sb.toString();
}
}


#### 结果 ### 完全不用String和StringBuilder库，只用Array

finalLength = count + (count / K) - ((count % K == 0)? 1 : 0)

#### 代码

class Solution {

private final char DASH = '-';

public String licenseKeyFormatting(String S, int K) {
char[] s = S.toCharArray();

// calculate number of alphanumeric characters
int count = 0;
for (int i = 0; i < s.length; i++) {
if (s[i] == DASH) { continue; }
count++;
}
if (count == 0) { return ""; }

// result array with certain length
char[] arr = new char[count + (count / K) - ((count % K == 0)? 1 : 0)];
// pointers
int wp = 0;                 // pointer on window of K
int sp = s.length - 1;      // pointer on input array
int ap = arr.length - 1;    // pointer on result array

while (sp >= 0) {
if (wp == K && ap > 0) {
arr[ap--] = DASH;
}
for (wp = 0; sp >= 0 && wp < K; wp++, sp--) {
while (sp >= 0 && s[sp] == DASH) { sp--; } // skip dash
if (sp < 0) { break; }
char c = s[sp];
if (c >= 'a' && c <= 'z') { // to uppercase
c -= 32;
}
arr[ap--] = c;
}
}
return new String(arr);
}
}


#### 结果 