LeetCode: License Key Formatting

Posted on January 17, 2018July 26, 2020 by braindenny

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)

Post Views: 5