จำนวนขั้นต่ำในการสร้างโซลูชัน Anagram Leetcode สองสตริง


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อเมซอน บลูมเบิร์ก ซิทริกซ์ ไมโครซอฟท์ Twitter
เชือก

คำชี้แจงปัญหา

ในปัญหานี้เราได้รับสอง เงื่อนไข "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' สิ่งนี้สามารถทำได้อย่างง่ายดายด้วยความช่วยเหลือของตารางแฮช

การดำเนินการตามจำนวนขั้นต่ำเพื่อสร้างโซลูชัน Anagram 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

การวิเคราะห์ความซับซ้อนของจำนวนขั้นต่ำในการสร้างสองสตริง Anagram Leetcode Solutions

ความซับซ้อนของเวลา

O (N) โดยที่ N = ความยาวของสตริง 's' & 't'

ความซับซ้อนของอวกาศ 

O (1) เนื่องจากมีอักขระที่ไม่ซ้ำกันจำนวน จำกัด ในทั้งสองสตริงเราจึงรู้ว่าพื้นที่หน่วยความจำยังคงคงที่