Python solution using deque - detailed explanation


  • 0
    G

    Solution with discussion https://discuss.leetcode.com/topic/74985/python-solution-using-deque-detailed-explanation

    License Key Formatting https://leetcode.com/problems/license-key-formatting/

    Solution using a deque

    • Start from the last character and add items to top of deque
    • Inset delimiter wher cnt %K == 0. cnt includes just character count and not "-".
    • Invariant: cnt first reaches K and in next iteration we test for adding "-". This ensures we do not add un-necessarily add a "-" at start.
    • Beware of boundary condition - do not insert "-" without inserting any other character in the queue.
    from collections import deque
    class Solution(object):
        def licenseKeyFormatting(self, S, K):
            """
            :type S: str
            :type K: int
            :rtype: str
            """
            q, cnt = deque(), 0
            for i in range(len(S)-1,-1,-1):
                if S[i] != "-":
                    if cnt % K == 0 and cnt > 0:
                        q.appendleft("-")
                        q.appendleft(S[i].upper())
                        cnt = 1
                    else:
                        q.appendleft(S[i].upper())
                        cnt += 1
            return "".join(q)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.