制作两个字符串的最小步骤数Anagram Leetcode解决方案


难度级别 易得奖学金
经常问 亚马逊 彭博 思杰 微软 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解决方案

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),因为两个字符串中的唯一字符数量都有限,所以我们知道存储空间保持不变。