首页 > 试题广场 >

判断两个字符串是否为变形词

[编程题]判断两个字符串是否为变形词
  • 热度指数：2913 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定两个字符串str1和str2，如果str1和str2中出现的字符种类出现的一样且每种字符出现的次数也一样，那么str1和str2互为变形词。请判断str1和str2是否为变形词。

输入描述:
输入包括3行，第一行包含两个整数n，m分别代表str1和str2的长度，第二行和第三行为两个字符串，分别代表str1和str2。


输出描述:
如果str1和str2互为变形词，请输出“true”，否则输出“false”。
示例1

输入

3 3
123
321

输出

true
示例2

输入

3 4
123
2331

输出

false

备注:
时间复杂度，空间复杂度。
算法知识视频讲解
添加回答
Java
码海泛舟头像 码海泛舟 
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static int n, m;
    static Map<Character, Integer> map1 = new HashMap<>();
    static Map<Character, Integer> map2 = new HashMap<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        String s1 = sc.next();
        String s2 = sc.next();
        boolean res = f(s1, s2);
        if (res) {
            System.out.println("true");
        } else {
            System.out.println("false");
        }
    }

    private static boolean f(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        for (int i = 0; i < s1.length(); i++) {
            char c = s1.charAt(i);
            if (map1.containsKey(c)) {
                int cnt = map1.get(c);
                map1.put(c, cnt + 1);
            } else {
                map1.put(c, 1);
            }
        }
        for (int i = 0; i < s2.length(); i++) {
            char c = s2.charAt(i);
            if (map2.containsKey(c)) {
                int cnt = map2.get(c);
                map2.put(c, cnt + 1);
            } else {
                map2.put(c, 1);
            }
        }
        for (int i = 0; i < s1.length(); i++) {
            char c = s1.charAt(i);
            int cnt1 = map1.get(c);
            if (!map2.containsKey(c)) return false;
            int cnt2 = map2.get(c);
            if (cnt1 != cnt2) return false;
        }
        return true;
    }
}
发表于 2020-07-06 10:29:21 回复(0)
Java
小比例福头像 小比例福
解题思路参考左神的解法，详见程序员代码面试指南。
ps:若有不妥之处，望请相互交流，多谢。 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        String str1 = sc.next();
        String str2 = sc.next();
        if (isDeformation(str1, str2) == true) {
            System.out.println("true");
        } else {
            System.out.println("false");
        }
    }
    public static boolean isDeformation(String str1, String str2) {
        //优先考虑判空操作
        if (str1 == null || str2 == null || str1.length() != str2.length()) {
            return false;
        }
        //定义一个整形数组map，用于存储每一个字符出现的次数。
        int[] map = new int[256];//如果字符个数足够多，可以申请一个散列表。
        for (int i = 0; i < str1.length(); i++) {
            //map数组存储每一个字符出现的次数
            map[str1.charAt(i)]++;
        }
        for (int i = 0; i < str2.length(); i++) {
            //如果map数组的值小于0，则返回false
            if (map[str2.charAt(i)]-- < 0) {
                return false;
            }
        }
        return true;
    }
}


发表于 2019-09-27 15:01:16 回复(3)
提交观点

问题信息

模拟
上传者：小小
难度：
2条回答 3644浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号