الحد الأدنى لعدد الخطوات لعمل سلسلتين Anagram Leetcode Solutions  


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون بلومبرغ سيتريكس Microsoft تويتر
خوارزميات الترميز المقابلة الشخصية مقابلة LeetCode LeetCodeSolutions خيط

المشكلة بيان  

في هذه المسألة ، لدينا اثنان سلاسل تتكون 's' & 't' من أحرف إنجليزية صغيرة. في إحدى العمليات ، يمكننا اختيار أي حرف في السلسلة "t" وتغييره إلى حرف آخر. نحن بحاجة إلى إيجاد الحد الأدنى لعدد مثل هذه العمليات لجعل 't' an إعادة ترتيب الأحرف من '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". يمكن تنفيذ ذلك بسهولة بمساعدة جدول التجزئة.

انظر أيضا
هامنج عن بعد Leetcode الحل

تنفيذ الحد الأدنى من الخطوات لعمل سلسلتين Anagram Leetcode Solutions

برنامج 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 Leetcode Solutions

تعقيد الوقت

O (N) ، حيث N = أطوال السلسلة النصية 's' & 't'.

تعقيد الفضاء 

O (1) ، نظرًا لوجود عدد محدود من الأحرف الفريدة في كلتا السلسلتين ، نعلم أن مساحة الذاكرة تظل ثابتة.

1