ຈໍານວນຂັ້ນຕ່ໍາສຸດທີ່ຈະເຮັດສອງວິທີແກ້ໄຂ Anagram Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon Bloomberg Citrix Microsoft Twitter
string

ຖະແຫຼງການບັນຫາ

ໃນບັນຫານີ້, ພວກເຮົາໄດ້ຮັບສອງຢ່າງ strings 's' & 't' ປະກອບດ້ວຍຕົວອັກສອນພາສາອັງກິດທີ່ນ້ອຍ. ໃນການປະຕິບັດງານຄັ້ງ ໜຶ່ງ, ພວກເຮົາສາມາດເລືອກຕົວລະຄອນໃດ ໜຶ່ງ ໃນສາຍ 't' ແລະປ່ຽນມັນໄປເປັນຕົວລະຄອນອື່ນ. ພວກເຮົາຕ້ອງຊອກຫາ ຈຳ ນວນ ຕຳ ່ສຸດທີ່ຂອງການ ດຳ ເນີນງານດັ່ງກ່າວເພື່ອເຮັດໃຫ້ 't' ເປັນ anagram ຂອງ 's'.

ຍົກຕົວຢ່າງ

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

ຈໍານວນຂັ້ນຕ່ໍາສຸດຂອງຂັ້ນຕອນທີ່ຈະເຮັດໃຫ້ສອງ Anagram ເບິ່ງຊ່ອຍແນ່

ວິທີການ

ມັນເປັນທີ່ຈະແຈ້ງວ່າຕົວລະຄອນທີ່ມີລັກສະນະດຽວກັນໃນທັງສອງສາຍບໍ່ ຈຳ ເປັນຕ້ອງມີການປະຕິບັດງານໃດໆ (ດັ່ງທີ່ພວກເຮົາຕ້ອງການມີ ໜ້າ ພ້ອມກັນຂອງພວກມັນ, ບໍ່ແມ່ນ ຄຳ ສັ່ງດຽວກັນ). ພາກສ່ວນທີ່ ສຳ ຄັນແມ່ນເຂົ້າໃຈວິທີທີ່ພວກເຮົາສາມາດແກ້ໄຂ ສຳ ລັບບັນດາຜູ້ທີ່ມີຄວາມສົນໃຈ.

ໃຫ້ເວົ້າວ່າກ່ອນອື່ນ ໝົດ ພວກເຮົາໄດ້ລຶບຕົວອັກສອນທັງ ໝົດ ທີ່ຢູ່ໃນ 'string' ທີ່ກົງກັບບາງຕົວອັກສອນໃນ 't' string, ແລະຫຼັງຈາກນັ້ນໄດ້ລຶບຕົວອັກສອນທີ່ສອດຄ້ອງກັນນັ້ນໄວ້ໃນສາຍ 't'. ຕົວຢ່າງ s =“ ginny”, t =“ harry”. ຫຼັງຈາກຖອດຕົວອັກສອນທີ່ກົງກັບທັງສອງເຊືອກ, s = "ginn", t = "harr". ຕອນນີ້, ມັນເຫັນໄດ້ຊັດວ່າທຸກໆຕົວລະຄອນໃນສາຍ 't' ຕ້ອງ ໄດ້ຮັບການປ່ຽນແປງເປັນບາງຕົວອັກສອນອື່ນໆເພື່ອໃຫ້ຕົວອັກສອນຂອງ 's' ມີຢູ່ໃນນັ້ນ.

ຈື່ໄວ້ວ່າພວກເຮົາໄດ້ລຶບຄູ່ທີ່ກົງກັນທັງ ໝົດ ໃນ 's' ແລະ 't' ແລ້ວ. ສະນັ້ນ, ມັນຈະບໍ່ມີຕົວລະຄອນໃນ 't' ທີ່ມີຢູ່ໃນ 's'. ນີ້ສາມາດປະຕິບັດໄດ້ງ່າຍໂດຍການຊ່ວຍເຫຼືອຂອງຕາຕະລາງ hash.

ການປະຕິບັດຕົວເລກຂັ້ນຕ່ໍາສຸດເພື່ອເຮັດສອງວິທີແກ້ໄຂ 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 Program

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

ຄວາມສັບສົນເວລາ

O (N), ບ່ອນທີ່ N = ຄວາມຍາວຂອງສາຍ 's' & 't'.

ຄວາມສັບສົນໃນອະວະກາດ 

O (1), ຍ້ອນວ່າມີ ຈຳ ນວນຕົວອັກສອນທີ່ບໍ່ຊ້ ຳ ກັນໃນສອງສາຍ, ພວກເຮົາຮູ້ວ່າພື້ນທີ່ຄວາມ ຈຳ ຍັງຄົງຢູ່.