可以应用哪些优化来减少查找最小编号的执行时间。将字符串转换为给定字符串的字谜的步骤？

Question

此要求是算法挑战的一部分。详情如下：

使用 Case/Requirement ：两个字符串即。 's' & 't' 仅包含小写英文字母且长度相等。字符串't'需要修改为字符串's'的变位词，替换't'中的字符。每一次替换都算作一个步骤。预期输出应该是所需的此类步骤的最少数量。

例子

示例输入：

s = "朋友"

t = "家庭"

预期输出：4

原因：将 'a'、'm'、'l' & 'y' 替换为 'r'、'e'、'n' & 'd' 任意顺序

我的方法

使用的数据结构：已使用散列概念，并采用 HashMap 为给定字符串中的所有字母及其频率创建名册

算法概述：首先为两个字符串创建字母表及其频率的映射。然后计算常见字母的频率与字符串 't' 中缺失的字母出现在字符串 's' 中的频率之间的差异之和。由于总和是所需步数的两倍，因此最终答案除以 2 并作为解决方案返回。

FYR 我的代码 :

package com.task;

import java.util.Map;
import java.util.HashMap;
import java.util.Scanner;

class Solution {

    Map<Character, Integer> createFreqMap(String s) {
        char[] arr = s.toCharArray();
        Map<Character, Integer> m = new HashMap<>();
        for(char c : arr) {
            m.put(c, m.getOrDefault(c, 0) + 1);
        }
        return m;
    }

    int diffMap(Map<Character, Integer> ms, Map<Character, Integer> mt) {
        int d = 0;
        // traverse first map for diff
        for(Character c : ms.keySet()) {
            if(mt.containsKey(c)) {
                d += (Math.abs(ms.get(c) - mt.get(c)));
            }
            else d += ms.get(c);
        }

        // traverse second map for diff
        for(Character c : mt.keySet()) {
            if(!ms.containsKey(c)) {
                d += mt.get(c);
            }
        }
        return d;
    }

    public int minSteps(String s, String t) {
        Map<Character, Integer> sFreqMap = createFreqMap(s);
        Map<Character, Integer> tFreqMap = createFreqMap(t);
        int d = diffMap(sFreqMap, tFreqMap);
        return (d/2);
    }
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String s = scan.nextLine();
        String t = scan.nextLine();
        Solution obj = new Solution();
        System.out.println(obj.minSteps(s, t));
    }
}

该代码工作正常并给出了我想要的解决方案，但是与其他参与者相比它很慢，那么如何才能减少执行时间呢？

Answer 1

首先你不需要遍历第二张地图

为了进一步优化这一点，您可以使用数组而不是地图。您只有 26 个可能的键，因此不会有任何内存问题。

public class App {

    int[] createFreqMap(String s) {
        char[] arr = s.toCharArray();
        int[] m = new int[26];
        for (char c : arr) {
            m[c - 'a']++;
        }
        return m;
    }

    int diffMap(int[] ms, int[] mt) {
        int d = 0;
        for (int i = 0; i < ms.length; i++) {
            d += Math.abs(ms[i] - mt[i]);
        }
        return d/2;
    }

    public int minSteps(String s, String t) {
        int[] sFreqMap = createFreqMap(s);
        int[] tFreqMap = createFreqMap(t);
        return diffMap(sFreqMap, tFreqMap);
    }

    public static void main(String[] args) {
        String s = "friend";
        String t = "family";
        App obj = new App();
        System.out.println(obj.minSteps(s, t));
    }
}

可以应用哪些优化来减少查找最小编号的执行时间。将字符串转换为给定字符串的字谜的步骤？

What optimizations could be applied to reduce the execution time of finding min no. of steps to convert a string into an anagram of a given string?

java

string

algorithm

anagram

data-structures