leetcode242. 有效的字母异位词,哈希表

2024-08-22 06:20

本文主要是介绍leetcode242. 有效的字母异位词,哈希表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

leetcode242. 有效的字母异位词

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。

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

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

提示:
1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母

在这里插入图片描述

目录

    • leetcode242. 有效的字母异位词
    • 题目分析
    • 算法步骤
    • 算法流程
    • 具体代码
    • 算法分析
    • 相似题目

题目分析

给定两个字符串 st,判断 t 是否是 s 的字母异位词。字母异位词是指由相同字母重排列形成的字符串。这个问题可以通过哈希表(或称为字典)来解决。

算法步骤

  1. 初始化一个无序哈希表 p
  2. 遍历字符串 s,将每个字符的出现次数存储在哈希表中。
  3. 遍历字符串 t,减少哈希表中对应字符的出现次数。
  4. 遍历哈希表 p,检查每个字符的出现次数是否为0。
  5. 如果所有字符的出现次数都为0,则返回 true,表示 ts 的字母异位词;否则返回 false

算法流程

开始
初始化无序哈希表p
遍历字符串s
遍历字符串t
遍历哈希表p
所有字符出现次数是否为0
返回true
返回false

具体代码

class Solution {
public:bool isAnagram(string s, string t) {unordered_map<char,int> p;for(int i=0;i<s.size();i++){p[s[i]]++;}for(int i=0;i<t.size();i++){p[t[i]]--;}for(auto q:p){if(q.second!=0) return false;}return true;}
};

算法分析

  • 时间复杂度: O(n),其中 n 是字符串 st 的长度之和。
  • 空间复杂度: O(1),因为哈希表的大小只取决于字符集的大小,对于英文字母而言,其大小是固定的。
  • 易错点: 在处理字符出现次数时,需要注意字符的ASCII值范围,确保所有字符都能被正确处理。

相似题目

题目链接
242. 有效的字母异位词https://leetcode.cn/problems/valid-anagram/
49. 字母异位词分组https://leetcode.cn/problems/group-anagrams/
剑指 Offer II 032. 有效的变位词https://leetcode.cn/problems/dKk3P7/

这篇关于leetcode242. 有效的字母异位词,哈希表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1095483

相关文章

Kali Linux安装实现教程(亲测有效)

《KaliLinux安装实现教程(亲测有效)》:本文主要介绍KaliLinux安装实现教程(亲测有效),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、下载二、安装总结一、下载1、点http://www.chinasem.cn击链接 Get Kali | Kal

Java如何将文件内容转换为MD5哈希值

《Java如何将文件内容转换为MD5哈希值》:本文主要介绍Java如何将文件内容转换为MD5哈希值的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java文件内容转换为MD5哈希值一个完整的Java示例代码代码解释注意事项总结Java文件内容转换为MD5

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

一文教你PyCharm如何有效地添加源与库

《一文教你PyCharm如何有效地添加源与库》在使用PyCharm进行Python开发的时候,很多时候我们需要添加库或者设置源,下面我们就来和大家详细介绍一下如何在PyCharm中添加源和库吧... 在使用PyCharm进行python开发的时候,很多时候我们需要添加库或者设置源。这些操作可以帮助我们更方便

OpenManus本地部署实战亲测有效完全免费(最新推荐)

《OpenManus本地部署实战亲测有效完全免费(最新推荐)》文章介绍了如何在本地部署OpenManus大语言模型,包括环境搭建、LLM编程接口配置和测试步骤,本文给大家讲解的非常详细,感兴趣的朋友一... 目录1.概况2.环境搭建2.1安装miniconda或者anaconda2.2 LLM编程接口配置2

Linux虚拟机不显示IP地址的解决方法(亲测有效)

《Linux虚拟机不显示IP地址的解决方法(亲测有效)》本文主要介绍了通过VMware新装的Linux系统没有IP地址的解决方法,主要步骤包括:关闭虚拟机、打开VM虚拟网络编辑器、还原VMnet8或修... 目录前言步骤0.问题情况1.关闭虚拟机2.China编程打开VM虚拟网络编辑器3.1 方法一:点击还原VM

查询SQL Server数据库服务器IP地址的多种有效方法

《查询SQLServer数据库服务器IP地址的多种有效方法》作为数据库管理员或开发人员,了解如何查询SQLServer数据库服务器的IP地址是一项重要技能,本文将介绍几种简单而有效的方法,帮助你轻松... 目录使用T-SQL查询方法1:使用系统函数方法2:使用系统视图使用SQL Server Configu

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (