Java教程

力扣242 有效的字母异位词

本文主要是介绍力扣242 有效的字母异位词,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

  • 题目链接
  • 源代码 github 地址
  • 1、题目要求
  • 2、思路分析
    • 2.1 方法一
    • 2.2 方法二
  • 3、执行代码
    • 3.1、方法一的代码实现
    • 3.2、方法二的代码实现
  • 4、问题反思
    • 4.1、关于方法二中的 for 循环的理解
  • 5、小结

题目链接

https://leetcode-cn.com/problems/valid-anagram/

源代码 github 地址

https://github.com/YIMEng-0/DataStructure

1、题目要求

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。

字母异位词的概念:
注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。
简单理解就是:两个字符串长度一样,构成字符串的每个字符只是排列的顺序不一样,含有的具体字符以及具体字符的个数是一样的;

示例 1:
输入: s = "anagram", t = "nagaram"
输出: true

示例 2:
输入: s = "rat", t = "car"
输出: false

2、思路分析

2.1 方法一

对于两个字符串里面的每个字符进行排序,然后比较排序后的结果,调用 Arrays.equals() 方法即可;
排序之前需要将字符串转换为 char 数组,这样子才能方便排序;

2.2 方法二

使用一个记录字符串中字符出现频次的数组,这个数组大小定义为 26 因为英语中存在 26 个字母,可以统计所有的字母字符串的情况;
对于字符串 s 来讲记录每个字符出现的次数,出现一次,记录频次的数组就会在相应的位置加一
对于字符串 t 来讲,记录每个字符出现的次数,出现一次,在记录频次的数字就会在相应的位置减一
如果记录频次的数组最终所有的元素都是 0 ,说明两个字符串是满足字母异位词的定义的;

在这里插入图片描述

3、执行代码

3.1、方法一的代码实现

    public static boolean isAnagram(String s, String t) {
        // 比较字符串的长度,长度不一致的话直接返回 false 即可
        if (s.length() != t.length()) {
            return false;
        }

        // 转换成为字符数组类型,方便对单个字符数组进行排序,查看里面的元素是否是相同的
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();

        // 进行排序处理
        Arrays.sort(str1);
        Arrays.sort(str2);

        // 进行比较即可,调用了 Arrays 里面的比较函数
        return Arrays.equals(str1, str2);
    }

3.2、方法二的代码实现

    public boolean isAnagram1(String s, String t) {
        int[] record = new int[26];

        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();

        for (int i = 0; i < str1.length; i++) {
            record[str1[i] - 'a'] += 1;
        }

        for (int i = 0; i < str2.length; i++) {
            record[str2[i] - 'a'] -= 1;
        }

        for (int i = 0; i < record.length; i++) {
            if (record[i] != 0) {
                return false;
            }
        }

        return true;
    }

4、问题反思

4.1、关于方法二中的 for 循环的理解

for (int i = 0; i < str1.length; i++) {
    record[str1[i] - 'a'] += 1;
}

str1 是字符串 s 转换成为 char[] 数组的结果,这样子可以方便使用char[]数组对字符串中的每个字符进行操作;

i < str1.length;是对于 s 字符串中所有字符出现的总频次;可以对于 s 字符串中每个字符都统计到;

record[str1[i] - 'a'] += 1; 写法
等价于 record[str1[i] - 'a'] ++;
等价于record[str1[i] - 'a'] = record[str1[i] - 'a'] + 1;不过后者理解起来可能没有前者理解起来方便;

record 是一个 int 数组,目的就是统计 字符串s 以及 字符串t 两个字符串中字符出现的次数

  • s 出现的字符出现一次,record 中对应的位置负责加一的操作;
  • t 字符串出现的字符出现一次,record 中对应的位置负责减一的操作;
  • 当 record 数组里面都是 0 的时候,增加的和减少的是相同的,说明满足字母异位词的定义;

5、小结

通过了排序的方式,以及使用记录数组的方式,可以实现字母异位词的判别。使用记录数组的方式,是对于这个问题的一个转换,大的字符串拆解成为小的字符,然后统计字符的个数,当统计字符个数的数组 record 元素都是 0 的时候,满足字母异位词的定义,输出结果为 true;

这篇关于力扣242 有效的字母异位词的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!