license-key-formatting.py

"""

482. License Key Formatting
Easy

You are given a license key represented as a string s that consists of only alphanumeric characters and dashes. The string is separated into n + 1 groups by n dashes. You are also given an integer k.

We want to reformat the string s 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 you should convert all lowercase letters to uppercase.

Return the reformatted license key.

 

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.
 

Constraints:

1 <= s.length <= 105
s consists of English letters, digits, and dashes '-'.
1 <= k <= 104

"""


# V0
# IDEA : BRUTE FORCE + STRTING OP
class Solution(object):
    def licenseKeyFormatting(self, s, k):
        # help func
        def help(_str):
            _res = ""
            i = 0
            _len = len(_str)
            while i < _len:
                tmp = s[i:i+k]
                print ("tmp = " + str(tmp))
                i = i+k
                _res = (_res + "-" + tmp)
            return _res.strip("-")       
        _s  = [ x.upper() if x.isalpha() else x for x in s.replace("-", "")  ]
        s = "".join(_s)
        # edge case
        if not s or k == len(s):
            return s
        # str op
        _len = len(s)
        res = ""
        print ("s = " + str(s))
        # if can split by k
        if _len % k == 0:
            res = help(s)
            res.strip("-")
        # else, (there is a remaining)
        else:
            _remain = _len % k
            resmin = s[:_remain]
            s = s[_remain:]
            res = help(s)
            res =  resmin + "-" + res
        return res.strip("-")

# V0'
# IDEA : inverse traversal + residual
class Solution(object):
    def licenseKeyFormatting(self, S, K):
        result = []
        for i in range(len(S))[::-1]:
            if S[i] == '-':
                continue
            if len(result) % (K + 1) == K:
                result += '-'
            result += S[i].upper()
        return "".join(result[::-1])

# V0''
# IDEA : string op + brute force
class Solution(object):
    def licenseKeyFormatting(self, s, k):
        # edge case
        if not s or not k:
            return s
        s = s.replace("-", "")
        s_ = ""
        for _ in s:
            if _.isalpha():
                s_ += _.upper()
            else:
                s_ += _

        s_ = list(s_)
        #print ("s_ = " + str(s_))
        s_len = len(s)
        remain = s_len % k
        #res = []
        res = ""
        tmp = ""
        # if s_len % k != 0
        while remain != 0:
            tmp += s_.pop(0)
            remain -= 1
        #res.append(tmp)
        res += (tmp + "-")
        tmp = ""
        # if s_len % k == 0
        for i in range(0, len(s_), k):
            #print (s_[i:i+k])
            #res.append(s_[i:i+k])
            res += ("".join(s_[i:i+k]) + "-")
        return res.strip("-")

# V0'''
# IDEA : GO THROUGH THE STRING FROM BACK,
#        -> SO NO NEED TO THINK ABOUT THE "len(S) % K > 1"  cases
class Solution:
    def licenseKeyFormatting(self, S, K):
        S = S.replace("-", "").upper()[::-1]
        return '-'.join(S[i:i+K] for i in range(0, len(S), K))[::-1]

# V0''''
# DEMO : range with gap
#    ...: for i in range(1,10, 2):
#    ...: ^Iprint (i)
#    ...:  
# 1
# 3
# 5
# 7
# 9
#
# IDEA:  
# -> use '#' to add back the remainder of len(S) % K 
# -> then go throughg S (with gap), and replace '#' with ''
class Solution(object):
    def licenseKeyFormatting(self, S, K):
        S = S.replace('-', '').upper()
        if len(S) % K:
            S = '#' * (K - len(S) % K) + S
        return '-'.join(S[x:x + K] for x in range(0, len(S), K)).replace('#', '')

# V1 
# http://bookshadow.com/weblog/2017/01/08/leetcode-license-key-formatting/
class Solution(object):
    def licenseKeyFormatting(self, S, K):
        """
        :type S: str
        :type K: int
        :rtype: str
        """
        S = S.replace('-', '').upper()
        if len(S) % K:
            S = '#' * (K - len(S) % K) + S
        return '-'.join(S[x:x + K] for x in range(0, len(S), K)).replace('#', '')

### Test case : dev 

# V1'
# https://leetcode.com/problems/license-key-formatting/discuss/131978/beats-100-python3-submission
class Solution:
    def licenseKeyFormatting(self, S, K):
        """
        :type S: str
        :type K: int
        :rtype: str
        """
        S = S.replace("-", "").upper()[::-1]
        return '-'.join(S[i:i+K] for i in range(0, len(S), K))[::-1]

# V1''
# https://leetcode.com/problems/license-key-formatting/discuss/96497/Python-solution
class Solution(object):
    def licenseKeyFormatting(self, S, K):
        """
        :type S: str
        :type K: int
        :rtype: str
        """
        S = S.upper().replace('-','')
        size = len(S)
        s1 = K if size%K==0 else size%K
        res = S[:s1]
        while s1<size:
            res += '-'+S[s1:s1+K]
            s1 += K
        return res

# V1'''
# https://leetcode.com/problems/license-key-formatting/discuss/175523/Concise-Python-Beats-100
class Solution:
    def licenseKeyFormatting(self, S, K):
        """
        :type S: str
        :type K: int
        :rtype: str
        """
        def chunks(l, n):
            for i in range(0, len(l), n):
                yield l[i:i+n]
        s = S[::-1].upper().replace('-', '')   
        return '-'.join(list(chunks(s, K)))[::-1]

# V2 
# Time:  O(n)
# Space: O(1)
class Solution(object):
    def licenseKeyFormatting(self, S, K):
        """
        :type S: str
        :type K: int
        :rtype: str
        """
        result = []
        for i in reversed(range(len(S))):
            if S[i] == '-':
                continue
            if len(result) % (K + 1) == K:
                result += '-'
            result += S[i].upper()
        return "".join(reversed(result))