Skip to content

Latest commit

 

History

History
147 lines (103 loc) · 5.57 KB

1347.md

File metadata and controls

147 lines (103 loc) · 5.57 KB

1347. 制造字母异位词的最小步骤数

Hi 大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之 leetcode 周赛题解。

这里是第 175 期的第 2 题,也是题目列表中的第 1347 题 -- 『制造字母异位词的最小步骤数』

题目描述

给你两个长度相等的字符串 st。每一个步骤中,你可以选择将 t 中的 任一字符 替换为 另一个字符

返回使 t 成为 s 的字母异位词的最小步骤数。

字母异位词 指字母相同,但排列不同的字符串。

示例 1:

输入:s = "bab", t = "aba"
输出:1
提示:用 'b' 替换 t 中的第一个 'a',t = "bba" 是 s 的一个字母异位词。

示例 2:

输入:s = "leetcode", t = "practice"
输出:5
提示:用合适的字符替换 t 中的 'p', 'r', 'a', 'i''c',使 t 变成 s 的字母异位词。

示例 3:

输入:s = "anagram", t = "mangaar"
输出:0
提示:"anagram""mangaar" 本身就是一组字母异位词。

示例 4:

输入:s = "xxyyzz", t = "xxyyzz"
输出:0

示例 5:

输入:s = "friend", t = "family"
输出:4

提示:

  • 1 <= s.length <= 50000
  • s.length == t.length
  • st 只包含小写英文字母

官方难度

MEDIUM

解决思路

题目的意思还是很直白的,其中最关键的一个信息就是,需要让 t 成为 s 的字母异位词。那么什么是字母异位词呢?即两个字符串包含的字母的种类和数量都一样。至于字母之间的排列顺序,这里上面官方的中文题目描述其实是有问题的,因为英文原文是 "with a different (or the same) ordering.",所以字母顺序其实是可以不同,也可以相同的。

既然没有了顺序的顾虑,那么我们面临的问题就只剩一个啦 -- 保证两个字符串中字母的种类和数量都一样。那么说到这里,我们第一件要做的事情其实已经非常明显了,就是对字符串进行字母频率统计。如何统计呢?相信看过周赛第一题的小伙伴可以轻松的想到,通过遍历字符串并结合字典计数,便可完成对于字符串中出现字母的种类和数量进行统计。

假设现在我们已经有了两个字符串的字母统计结果,我们应该如何找到最小的替换步数呢?这里我们可以想象一下,对比这两个字符串的字母统计结果,其实只可能会出现两种情况:

  • t 中某个字母的数量比 s 中多。
  • t 中某个字母的数量比 s 中少。

由于我们每一次替换字母是无任何要求的,所以我们可以将任何一个 ts 多的字母替换为一个 ts 少的字母。并且,由于 ts 这两个字符串的长度一定相等,所以我们这里多出的数量和少的数量一定是相等的。也就是说,我们最终要找的最少的替换步数,其实就是这个多出的数量或者少的数量。

直接方案

基于上面分析的思路,我们可以得到如下的流程:

  1. 遍历两个字符串,得到各自的字母统计结果。
  2. 对比两个统计结果,得到 t 字符串中比 s 多的数量。

基于这个流程,我们可以实现类似下面的代码:

const minSteps = (s, t) => {
  const BASE = 97;
  const count1 = new Int32Array(26);
  const count2 = new Int32Array(26);
  for (let i = 0; i < s.length; ++i) {
    ++count1[s.charCodeAt(i) - BASE];
  }
  for (let i = 0; i < t.length; ++i) {
    ++count2[t.charCodeAt(i) - BASE];
  }
  let step = 0;
  for (let i = 0; i < 26; ++i) {
    step += count1[i] > count2[i] ? count1[i] - count2[i] : 0;
  }
  return step;
};

优化

上面的代码里,我们统计了两次计数结果,并且也遍历了两次字符串长度。那么我们是否可以削减一半呢?

这时我们注意一下最终我们需要的是什么,会发现其实我们要的只是两者的差值,而它们的数量究竟是多少其实我们是不关心的。基于这个想法,我们可以尝试直接在一次遍历中计算差值,而不是统计总数量。

基于上面分析的思路,我们可以得到如下的流程:

  1. 遍历一次字符串的长度。
  2. 对于两个字符串中出现的字母,计算对应字母的统计差值。
  3. 对差值中的正数求和并返回。

基于这个流程,我们可以实现类似下面的代码:

const minSteps = (s, t) => {
  const BASE = 97;
  const count = new Int32Array(26);
  for (let i = 0; i < s.length; ++i) {
    ++count[s.charCodeAt(i) - BASE];
    --count[t.charCodeAt(i) - BASE];
  }
  let step = 0;
  for (let i = 0; i < 26; ++i) {
    count[i] > 0 && (step += count[i]);
  }
  return step;
};

总结

这道题内容非常直白,而核心的点就在于最终需求的要求。一旦我们分析明白了这个需求,我们也就可以很容易的基于此得到实现方案。

其实熟悉了的话,完全可以直接写出上面优化版本的代码,小猪在比赛中也是直接提交的这个代码。不过为了展示这个优化的思路,小猪在这里还是先给出了直接方案的代码。小猪是不是很贴心鸭,嘿嘿嘿~ 快夸夸小猪,嘤嘤嘤 >.<

相关链接

我的微信公众号:张小猪粉鼻子