מספר פעולות מינימלי להכנת שתי מיתרים פתרונות ליקוד לאגרמה  


רמת קושי קַל
נשאל לעתים קרובות אמזון בעברית בלומברג Citrix מיקרוסופט טויטר
אלגוריתמים קידוד ראיון אישי הוכחת ראיונות LeetCode LeetCodeSolutions מחרוזת

הצהרת בעיה  

בבעיה זו נותנים לנו שניים מחרוזות 's' & 't' המורכב מדמויות אנגליות קטנות. בפעולה אחת, אנו יכולים לבחור כל תו במחרוזת 't' ולשנות אותו לתו אחר. עלינו למצוא את המספר המינימלי של פעולות כאלה כדי להפוך את 't' ל- אנגרמה של 's'.

דוגמה

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

מספר השלבים המינימלי להכנת שני מיתרים

גישה  

ברור כי הדמויות זהות בשני המיתרים אינן דורשות פעולות כלשהן (מכיוון שאנו זקוקים לנוכחותן בו זמנית, ולא לאותו הסדר). החלק החשוב הוא להבין כיצד נוכל לפתור עבור שאר השטרות.

נניח שניקינו תחילה את כל התווים במחרוזות התואמות לדמות כלשהי במחרוזת 't', ואז מחקנו את התווים המתאימים במחרוזת 't'. דוגמה s = "ginny", t = "harry". לאחר הסרת תווים תואמים בשני המחרוזות, s = "ginn", t = "harr". עכשיו, ברור שכל דמות במחרוזת 't' צריך ישתנה לדמות אחרת, כך שגם הדמויות של 's' נוכחות בה.

זכור שכבר הסרנו את כל זוגות ההתאמות ב- 's' ו- 't'. לכן, לא תהיה דמות ב- 't' שנמצאת ב- 's'. ניתן ליישם זאת בקלות בעזרת טבלת hash.

ראה גם
פיתרון מרחק Hamming מרחק קוד

יישום מספר הצעדים המינימלי לייצור שתי מיתרים פתרונות 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), מכיוון שיש מספר מוגבל של תווים ייחודיים בשני המיתרים, אנו יודעים שמרחב הזיכרון נשאר קבוע.