حداقل تعداد مراحل برای ساخت دو رشته Anagram Leetcode Solutions  


سطح دشواری ساده
اغلب در آمازون بلومبرگ خودتان هستید؟ مایکروسافت توییتر
الگوریتم برنامه نویسی مصاحبه مصاحبه آماده LeetCode LeetCodeSolutions رشته

بیان مسأله  

در این مشکل ، دو مورد به ما داده می شود رشته های 's' & 't' از حروف کوچک انگلیسی تشکیل شده است. در یک عملیات می توانیم هر رشته را در رشته 't' انتخاب کنیم و آن را به کاراکتر دیگری تغییر دهیم. برای ایجاد "t" باید حداقل تعداد چنین عملیاتی را پیدا کنیم انجماد از 's'

مثال

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

حداقل تعداد مراحل ساخت دو رشته Anagramسنجاق

روش  

واضح است که کاراکترهایی که در هر دو رشته یکسان هستند به هیچ عملیاتی احتیاج ندارند (همانطور که ما به حضور همزمان آنها نیاز داریم ، نه ترتیب یکسان). قسمت مهم این است که درک کنیم چگونه می توانیم برای بقیه کاراکترها حل کنیم.

بگذارید بگوییم ما ابتدا همه نویسه های رشته "" را که با برخی از نویسه ها در رشته "t" مطابقت دارند پاک کردیم و سپس آن شخصیت های مربوطه را در رشته "t" حذف کردیم. مثال s = "جینی" ، t = "هری". پس از حذف کاراکترهای منطبق در هر دو رشته ، s = "ginn" ، t = "harr". اکنون واضح است که هر کاراکتر در رشته "t" باید به کاراکتر دیگری تغییر یابد تا شخصیت های 's نیز در آن وجود داشته باشد.

به یاد داشته باشید که ما قبلاً همه جفتهای مسابقه را در 's' و 't' حذف کرده بودیم. بنابراین ، هیچ شخصیتی در "t" وجود نخواهد داشت که در "s" وجود داشته باشد. این به راحتی می تواند با کمک یک جدول هش اجرا شود.

همچنین مشاهده کنید
راه حل کدگذاری فاصله Hamming

اجرای حداقل تعداد مراحل ساخت راه حل های کد Leagram کد دو رشته

برنامه 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

تجزیه و تحلیل پیچیدگی حداقل تعداد مراحل برای ساخت دو رشته راه حل کد کد Anagram

پیچیدگی زمان

O (N) ، جایی که N = طول رشته ها 'و' t '.

پیچیدگی فضا 

O (1) ، چون تعداد نویسه های منحصر به فردی در هر دو رشته وجود دارد ، می دانیم که فضای حافظه ثابت می ماند.

1