製作兩個字符串的最小步驟數Anagram Leetcode解決方案  


難度級別 容易獎學金
經常問 亞馬遜 彭博社 思傑 Microsoft微軟 Twitter
算法 編碼 訪問 面試準備 力碼 力碼解決方案

問題陳述  

在這個問題上,我們得到兩個 字符串 's'和't'由小寫英文字符組成。 在一個操作中,我們可以選擇字符串“ t”中的任何字符並將其更改為其他字符。 我們需要找到最小數量的此類操作,以使“ t”成為 字謎 的“ s”。

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

製作兩個字符串字謎的最小步驟數

途徑  

顯然,兩個字符串中相同的字符不需要任何操作(因為我們需要它們同時存在,而不是相同的順序)。 重要的部分是了解我們如何解決其餘字符。

假設我們首先清除了字符串“ s”中與字符串“ t”中某個字符匹配的所有字符,然後刪除了字符串“ t”中的那些對應字符。 示例s =“ ginny”,t =“ harry”。 刪除兩個字符串中的匹配字符後,s =“ ginn”,t =“ harr”。 現在,很明顯,字符串“ t”中的每個字符 必須的, 更改為其他字符,以便在其中也顯示“ s”字符。

請記住,我們已經刪除了“ s”和“ t”中的所有匹配對。 因此,“ s”中不會出現“ t”中的字符。 這可以通過哈希表輕鬆實現。

也可以看看
海明距離Leetcode解決方案

最小步數的實現,以使兩個字符串類似圖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解決方案

時間複雜度

O(N),其中N =字符串“ s”和“ t”的長度。

空間複雜度 

O(1),因為兩個字符串中的唯一字符數量都有限,所以我們知道存儲空間保持不變。

1