算法题[leetcode-2186]使两字符串互为字母异位词的最少步骤数

题意

给你两个字符串 s 和 t。在一步操作中，你可以给 s 或者 t 追加 任一字符 。

返回使 s 和 t 互为 字母异位词 所需的最少步骤数。

字母异位词 指字母相同但是顺序不同（或者相同）的字符串。
示例 1：

输入：s = “leetcode”, t = “coats”
输出：7
解释：

• 执行 2 步操作，将 “as” 追加到 s = “leetcode” 中，得到 s = “leetcodeas” 。
• 执行 5 步操作，将 “leede” 追加到 t = “coats” 中，得到 t = “coatsleede” 。
  “leetcodeas” 和 “coatsleede” 互为字母异位词。
  总共用去 2 + 5 = 7 步。
  可以证明，无法用少于 7 步操作使这两个字符串互为字母异位词。

分析

统计2字符串各字母出现的次数，把2个字符串的字母补充成一样即可。2边字符串各字母的差异数就是要操作的步骤数。

代码

class Solution {
    public int minSteps(String s, String t) {

        int[] chCntArrS = new int[26];
        int[] chCntArrT = new int[26];
        for (int i = 0; i < s.length(); i++) {
            chCntArrS[s.charAt(i)-'a']++;
        }
        
        for (int i = 0; i < t.length(); i++) {
            chCntArrT[t.charAt(i)-'a']++;
        }
        
        int cnt=0;
        for (int i = 0; i < 26; i++) {
             cnt+=Math.abs(chCntArrS[i]-chCntArrT[i]);
        }
        return cnt;
    }

    public int minSteps2(String s, String t) {

        int[] chCntArr = new int[26];
        for (int i = 0; i < s.length(); i++) {
            chCntArr[s.charAt(i)-'a']++;
        }
        
        for (int i = 0; i < t.length(); i++) {
            chCntArr[t.charAt(i)-'a']--;
        }
        
        int cnt=0;
        for (int i = 0; i < 26; i++) {
            cnt+=Math.abs(chCntArr[i]);

        }
        return cnt;
    }
}

题目地址：

LeetCode