නූල් දෙකක් සෑදීම සඳහා අවම පියවර ගණන ඇනග්‍රෑම් ලීට්කෝඩ් විසඳුම්


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇමේසන් බ්ලූම්බර්ග් Citrix මයික්රොසොෆ්ට් ට්විටර්
String

ගැටළු ප්රකාශය

මෙම ගැටලුවේදී අපට දෙකක් ලබා දී ඇත නූල් කුඩා අකුරු සහිත ඉංග්‍රීසි අක්ෂර වලින් සමන්විත වේ. එක් මෙහෙයුමක දී, අපට 'ටී' නූලෙහි ඕනෑම අක්ෂරයක් තෝරාගෙන එය වෙනත් අක්ෂරයකට වෙනස් කළ හැකිය. 'T' බවට පත් කිරීම සඳහා එවැනි අවම මෙහෙයුම් සංඛ්‍යාවක් අප විසින් සොයාගත යුතුය ඇන්ග්රෑම් ගේ 'ගේ'.

උදාහරණයක්

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

නූල් දෙකක් සෑදීමට අවම පියවර ගණන ඇනග්‍රෑම්

ප්රවේශය

නූල් දෙකෙහිම එක හා සමාන වන අක්ෂරවලට කිසිදු මෙහෙයුමක් අවශ්‍ය නොවන බව පැහැදිලිය (අපට ඒවායේ එකවර සිටීම අවශ්‍ය බැවින් එකම අනුපිළිවෙලක් නොවේ). වැදගත් කොටස වන්නේ ඉතිරි ප්‍ර .ප්ති සඳහා අපට විසඳිය හැක්කේ කෙසේද යන්න තේරුම් ගැනීමයි.

'ටී' නූලෙහි කිසියම් අක්ෂරයකට ගැලපෙන 'අකුරු' හි ඇති සියලුම අක්ෂර අපි මුලින් ඉවත් කර, පසුව 'ටී' නූලෙහි ඇති අනුරූප අක්‍ෂර මකා දැමුවෙමු. උදාහරණ s ​​= “ජිනි”, ටී = “හැරී”. නූල් දෙකෙහිම ගැලපෙන අක්ෂර ඉවත් කිරීමෙන් පසු, s = “ජින්”, ටී = “හාර්”. දැන්, සෑම අක්ෂරයක්ම 'ටී' බව පැහැදිලිය කල යුතු වෙනත් අක්ෂරයකට වෙනස් කළ යුතු අතර එමඟින් 'ගේ' අක්ෂර ද එහි ඇත.

'S' සහ 't' හි ඇති සියලුම ගැලපීම් අපි දැනටමත් ඉවත් කර ඇති බව මතක තබා ගන්න. එබැවින්, 's' හි ඇති 't' හි කිසිදු චරිතයක් නොමැත. හැෂ් මේසයක ආධාරයෙන් මෙය පහසුවෙන් ක්‍රියාත්මක කළ හැකිය.

නූල් දෙකක් සෑදීම සඳහා අවම පියවර ගණනක් ක්‍රියාත්මක කිරීම ඇනග්‍රෑම් ලීට්කෝඩ් විසඳුම්

සී ++ වැඩසටහන

#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

නූල් දෙකක් සෑදීම සඳහා අවම පියවර ගණනක සංකීර්ණතා විශ්ලේෂණය ඇනග්‍රෑම් ලීට්කෝඩ් විසඳුම්

කාල සංකීර්ණත්වය

ඕ (එන්), එහිදී එන් = 's' සහ 't' නූල් වල දිග.

අභ්‍යවකාශ සංකීර්ණතාව 

O (1), නූල් දෙකෙහිම අද්විතීය අක්ෂර සංඛ්‍යාවක් සීමිත බැවින්, මතක අවකාශය නියතව පවතින බව අපි දනිමු.