Хоёр мөрт анаграмм Leetcode шийдлийг гаргах алхамуудын хамгийн бага тоо


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны Bloomberg Citrix Microsoft- Twitter
String

Асуудлын мэдэгдэл

Энэ асуудалд бид хоёрыг өгдөг мөр Англи хэлний жижиг үсгүүдээс бүрдэх 's' & 't'. Нэг үйлдэл дээр бид 't' мөрийн дурын тэмдэгтийг сонгож өөр тэмдэгт болгон өөрчлөх боломжтой. 'T' an болгохын тулд бид ийм үйлдлийн хамгийн бага тоог олох хэрэгтэй anagram 'ийн'.

Жишээ нь

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

Хоёр мөрт анаграм хийх алхамуудын хамгийн бага тоо

арга барил

Хоёр мөрөнд адилхан байгаа тэмдэгтүүд нь ямар ч үйлдэл шаарддаггүй нь тодорхой байна (бидэнд ижил дараалал биш, нэгэн зэрэг орших шаардлагатай байдаг). Чухал хэсэг бол үлдсэн дүрсийг хэрхэн яаж шийдэж болохыг ойлгох явдал юм.

Эхлээд бид 's' мөрийн зарим тэмдэгттэй тохирох бүх тэмдэгтүүдийг арилгаад дараа нь 't' мөрийн харгалзах тэмдэгтүүдийг устгалаа гэж хэлье. Жишээ s = "жинни", t = "харри". Хоёр мөрт тохирох тэмдэгтүүдийг арилгасны дараа s = “ginn”, t = “harr”. Одоо 't' мөрийн тэмдэгт бүр тодорхой болох нь дамжиггүй байх ёстой өөр тэмдэгт болгон өөрчилсөн тул 's' тэмдэгтүүд мөн дотор нь байх болно.

Бид 's' ба 't' бүх хос тохиргоог аль хэдийн хассан байсныг санаарай. Тэгэхээр 's' дотор байгаа 't' тэмдэгт байхгүй болно. Үүнийг хэш хүснэгтийн тусламжтайгаар хялбархан хэрэгжүүлж болно.

Хоёр мөрт анаграмм Leetcode шийдлийг гаргах хамгийн бага тооны алхамыг хэрэгжүүлэх

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;
}

Java програм

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

Хоёр мөрт анаграмм Leetcode шийдлийг гаргах хамгийн бага тооны нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N), хаана N = 's' & 't' мөрийн урт.

Сансрын нарийн төвөгтэй байдал 

O (1), хоёулаа хоёуланд нь хязгаарлагдмал тооны өвөрмөц тэмдэгтүүд байдаг тул санах ойн зай тогтмол байдгийг бид мэднэ.