License Key Formatting

Similar Problems:

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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

// https://code.dennyzhang.com/license-key-formatting // Basic Ideas: two pass: from left to right // // Complexity: Time O(n), Space O(n) func licenseKeyFormatting(S string, K int) string { l := []rune{} for _, ch := range S { if ch == '-' { continue } if ch >= 'a' && ch <= 'z' { ch = ch+('A'-'a') } l = append(l, ch) } l2 := []rune{} // only one group if len(l) <= K { l2 = l } else { i:=len(l)%K if i == 0 { i = K } for j:=0;j<len(l); j++ { l2 = append(l2, l[j]) // no need '-' for the last group if j==len(l)-1 { continue } if (j-i+1)%K == 0 { l2 = append(l2, '-') } } } return string(l2) }

// https://code.dennyzhang.com/license-key-formatting // Basic Ideas: two pass: from right to left // // Complexity: Time O(n), Space O(n) func licenseKeyFormatting(S string, K int) string { l := []rune{} for i, count:=len(S)-1,K; i>=0; i-- { ch := rune(S[i]) if ch == '-' { continue } if ch >= 'a' && ch <= 'z' { ch = ch+('A'-'a') } l = append(l, ch) count-- if count == 0 { l = append(l, '-') count = K } } if len(l)>0 && l[len(l)-1] == '-' { l = l[0:len(l)-1] } l2 := make([]rune, len(l)) for i:=len(l)-1; i>=0; i-- { l2[len(l)-1-i] = l[i] } return string(l2) }

## https://code.dennyzhang.com/license-key-formatting ## Basic Ideas: Get the length of non-dash string ## Then we know how many dash we need ## Move from right to left with two pointers ## Complexity: Time O(n), Space O(n) (If list instead of string, we can solve O(1) space) class Solution(object): def licenseKeyFormatting(self, S, K): """ :type S: str :type K: int :rtype: str """ length = len(S) count_str = length - S.count('-') count_group = count_str/K if count_str % K != 0: count_group += 1 l = [None] * (count_str + count_group - 1) # get result from the right to left index, count = len(l)-1, K for i in xrange(length-1, -1, -1): if index == -1: break if count == 0: l[index] = '-' index, count = index-1, K ch = S[i] if ch != '-': l[index] = ch.upper() index, count = index-1, count-1 return ''.join(l) # s = Solution() # s.licenseKeyFormatting("--a-a-a-a--", 2)