दुई स्ट्रिंगहरू अनग्राम लेटकोड समाधानहरू बनाउन चरणहरूको न्यूनतम संख्या


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन ब्लूमबर्ग citrix माइक्रोसफ्ट twitter
घागो

समस्या वक्तव्य

यस समस्यामा हामीलाई दुई दिइयो तार लोअर केस अंग्रेजी वर्णहरू समावेश भएको 's' & 't'। एउटा अपरेशनमा, हामी स्ट्रिंग 't' मा कुनै पनि वर्ण छनौट गर्न सक्दछौं र यसलाई केहि अन्य क्यारेक्टरमा परिवर्तन गर्न सक्दछौं। हामीले त्यस्ता अपरेशनहरूको न्यूनतम संख्या खोज्नु पर्छ 't' an बनाउन anagram को 's'

उदाहरणका

s = "bab", t = "aba"
1
s = "leetcode", t = "practice"
5

दुई स्ट्रिंगहरू अनग्राम बनाउन चरणहरूको न्यूनतम संख्या

दृष्टिकोण

यो स्पष्ट छ कि दुबै तारमा समान चरित्रहरूलाई कुनै अपरेसनको आवश्यक पर्दैन (किनकि हामीलाई तिनीहरूको एक साथ उपस्थिति चाहिन्छ, समान क्रम होइन)। महत्त्वपूर्ण कुरा यो बुझ्नको लागि हामी कसरी बाँकी चार्टरहरूका लागि समाधान गर्न सक्छौं।

मानौं हामी स्ट्रिंग 's' मा सबै क्यारेक्टरहरू क्लियर गर्यौं जुन स्ट्रिंग 't' मा केहि क्यारेक्टरसँग मेल खान्छ, र त्यसपछि ती स्ट्रिंग 't' मा मिल्दो अक्षरहरू मेटाईदियो। उदाहरण s = "ginny", t = "Harry"। दुबै स्ट्रि inमा मिल्ने क्यारेक्टरहरू हटाएपछि, s = "ginn", t = "harr"। अब, यो स्पष्ट छ कि स्ट्रिंग 't' मा प्रत्येक चरित्र पर्छ केहि अन्य चरित्रमा परिवर्तन गर्नुहोस् ताकि 's' का चरित्रहरू पनि यसमा उपस्थित हुन्छन्।

याद गर्नुहोस् कि हामीले पहिले नै 's' र 't' मा सबै जोडाहरू हटाएका थियौं। त्यसो भए, त्यहाँ 't' मा कुनै चरित्र छैन जुन 's' मा अवस्थित छ। यो सजिलैसँग ह्याश तालिकाको सहयोगमा कार्यान्वयन गर्न सकिन्छ।

दुई स्ट्रिंगहरू अनग्राम लेटकोड समाधानहरू बनाउन न्यूनतम चरणहरूको कार्यान्वयन

C ++ कार्यक्रम

#include <bits/stdc++.h>

using namespace std;

int minSteps(string s, string t) {
    unordered_map <int , int> f;
    int ans = 0;
    for(char &c : s) {
        f[c - 'a']++;
    }

    for(char &c : t) {
        f[c - 'a']--;
    }

    for(auto &c : f) {
        if(c.second != 0)
            ans++;
    }

    return ans / 2;
}

int main() {
    string s = "bab" , t = "aba";
    cout << minSteps(s , t) << endl;
    return 0;
}

जावा कार्यक्रम

import java.util.*;
import java.io.*;
import java.util.Hashtable;
import java.util.Set;
import java.util.Iterator;

class anagrams {
    public static void main(String args[]) {
        String s = "bab" , t = "aba";
        System.out.println(minSteps(s , t));
    }

    public static int minSteps(String s , String t) {

        Hashtable <Character , Integer> f = new Hashtable<>();
        int ans = 0;
        for(char c : s.toCharArray()) {
            f.put(c , f.getOrDefault(c , 0) + 1);
        }

        for(char c : t.toCharArray()) {
            f.put(c , f.getOrDefault(c , 0) - 1);
        }

        for(char c = 'a' ; c <= 'z' ; c++) {
            if(f.containsKey(c) && f.get(c) != 0) {
                ans += Math.abs(f.get(c));
            }
        }

        return ans / 2;
    }
}
1

दुई स्ट्रिंगहरू अनग्राम लेटकोड समाधानहरू बनाउन न्यूनतम चरणहरूको जटिलता विश्लेषण

समय जटिलता

O (N), जहाँ एन = स्ट्रिंग 's' र 't' को लम्बाई।

ठाउँ जटिलता 

हे (१), किनकि त्यहाँ दुबै स्ट्रिंगहरूमा सीमित संख्यामा अद्वितीय क्यारेक्टरहरू छन्, हामी जान्दछौं कि मेमोरी स्पेस स्थिर रहन्छ।