लाइसेंस कुंजी स्वरूपण Leetcode समाधान


कठिनाई स्तर आसान
में अक्सर पूछा एक राजधानी गूगल
तार StringBuilder

समस्या का विवरण

समस्या "लाइसेंस कुंजी स्वरूपण" में, इनपुट में एक होता है स्ट्रिंग पात्रों की, एक लाइसेंस कुंजी का प्रतिनिधित्व। प्रारंभ में, स्ट्रिंग को बीच में N डैश द्वारा N + 1 समूहों (शब्दों) में अलग किया जाता है। हमें एक पूर्णांक K भी दिया जाता है, और लक्ष्य स्ट्रिंग को प्रारूपित करना है जैसे कि प्रत्येक समूह में ठीक K अक्षर होते हैं, पहले वाले को छोड़कर, जिसे K से कम वर्णों की अनुमति है। '(डैश) और केवल बड़े अक्षर हैं।

उदाहरण

S = "5F3Z-2e-9-w", K = 4
5F3Z-2E9W
S = "2-5g-3-J", K = 2
2-5G-3J

दृष्टिकोण

यह सहज है कि हमें स्ट्रिंग एस (इनपुट) में पिछड़ते हुए एक नया स्ट्रिंग बनाना चाहिए। यह महत्वपूर्ण है क्योंकि हम जानते हैं कि पहले समूह को छोड़कर, अन्य सभी समूहों को उनमें बिल्कुल 'के' अक्षर होने चाहिए। यदि हम वापस स्ट्रिंग एस में iterate, हम बनाए रख सकते हैं एक का मुकाबला जो किसी समूह में जोड़े गए वर्णों की संख्या की गणना रखता है। यदि यह किसी भी क्षण 'के' के बराबर हो जाता है, तो हम इसे वापस शून्य पर रीसेट कर सकते हैं। इस तरह हम नए स्ट्रिंग में तत्वों को जोड़ते रहते हैं और इसे वापस करने से पहले, हम इसे ऑर्डर प्राप्त करने के लिए उल्टा कर देते हैं।

लाइसेंस कुंजी स्वरूपण Leetcode समाधान का कार्यान्वयन

C ++ प्रोग्राम

#include <bits/stdc++.h>

using namespace std;

string licenseKeyFormatting(string s , int k) {
    string ans;
    int cnt = 0 , n = s.size();

    for(int i = n - 1 ; i >= 0 ; i--) {
        if(s[i] != '-') {
            if(cnt == k) {
                ans += '-';
                cnt = 0;
            }
            cnt++;
            if(s[i] >= 'a' && s[i] <= 'z') {
                s[i] += 'A' - 'a';
            }
            ans += s[i];
        }
    }

    reverse(ans.begin() , ans.end());
    return ans;
}

int main() {
    string s = "5F3Z-2e-9-w";
    int K = 4;
    cout << licenseKeyFormatting(s, K) << endl;
    return 0;
}

जावा प्रोग्राम

import java.lang.*;
import java.io.*;
import java.util.*;

class license_key {
    public static void main(String args[]) {
        String s = "5F3Z-2e-9-w";
        int K = 4;
        System.out.println(licenseKeyFormatting(s , K));
    }

    public static String licenseKeyFormatting(String s , int k) {
        StringBuilder ans = new StringBuilder();
        int cnt = 0 , n = s.length();

        char c;
        for(int i = n - 1 ; i >= 0 ; i--) {
            c = s.charAt(i);
            if(c != '-') {
                if(cnt == k) {
                    ans.append('-');
                    cnt = 0;
                }
                cnt++;
                if(c >= 'a' && c <= 'z') {
                    c += 'A' - 'a';
                }
                ans.append(c);
            }
        }
        return ans.reverse().toString();
    }
}
5F3Z-2E9W

लाइसेंस कुंजी स्वरूपण Leetcode समाधान की जटिलता विश्लेषण

समय जटिलता

ओ (एन), एन = स्ट्रिंग की लंबाई। कार्यक्रम रैखिक है क्योंकि हम एक बार स्ट्रिंग को पुनरावृत्त करते हैं।

अंतरिक्ष जटिलता 

O (1), जैसा कि हम निरंतर मेमोरी स्पेस का उपयोग करते हैं।