当前位置: 首页 > article >正文

LeetCode 242 - 有效的字母异位词

题目描述

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

解题思路

要判断两个字符串是否为字母异位词,可以统计两个字符串中每个字符的数量,然后比较两个计数器是否相等。可以利用哈希表来记录每个字符出现的次数,遍历第一个字符串时增加计数,遍历第二个字符串时减少计数。最终检查哈希表中所有的计数器是否为0,如果是,则说明两个字符串是字母异位词。

算法实现

C++实现

class Solution {
public:
    bool isAnagram(string s, string t) {
        int hash[26]={0};
        for(int i=0;i<s.size();i++)
        {
            hash[s[i]-'a']++;
        }
        for(int i=0;i<t.size();i++)
        {
            hash[t[i]-'a']--;
        }
        for(int i=0;i<26;i++)
        {
            if(hash[i]!=0)
            {
                return false;
            }
        }
        return true;
    }
};
复杂度分析
  • 时间复杂度:O(n),其中 n 为字符串的长度。遍历字符串两次,哈希表的插入和查询操作的时间复杂度均为 O(1)。
  • 空间复杂度:O(1),由于只使用了常数额外空间,哈希表的大小最多为26个小写字母。
总结

通过使用哈希表记录字符出现的次数,我们可以高效地判断两个字符串是否为字母异位词。这种方法减少了额外内存的消耗,同时在线性时间复杂度内(O(n))完成了判断操作


http://www.kler.cn/a/372690.html

相关文章:

  • Flink + Kafka 实现通用流式数据处理详解
  • docker-minio启动参数
  • vue打包项目通过docker部署nginx服务
  • 如何有效提升MySQL大表分页查询效率(本文以一张900万条数据体量的表为例进行详细解读)
  • 【机器学习】Lesson3 - 逻辑回归(LR)二分类
  • 深度学习案例:带有一个隐藏层的平面数据分类
  • (done) 什么 RPC 协议? remote procedure call 远程调用协议
  • Comsol基于亥姆霍兹声学超材料的通风式低频吸声器
  • 【Linux】文件切割排序 cut sort
  • 微信小程序元素水平居中或垂直居中
  • vue打包项目直接输出压缩包,方便部署线上
  • HCIP-HarmonyOS Application Developer V1.0 笔记(二)
  • 问题记录01
  • Oracle视频基础1_1.1练习
  • C# 企业微信机器人推送消息 windows服务应用程序的使用
  • ComfyUI - ComfyUI 工作流中集成 SAM2 + GroundingDINO 处理图像与视频 教程
  • docker-高级(待补图)
  • 百度SEO中的关键词密度与内容优化研究【百度SEO专家】
  • 职业技术学校新出路,无人机飞手考证、组装、调试全面提高市场就业率
  • Qt:信号和槽
  • leetcode动态规划(二十三)-打家劫舍III
  • 【Python学习计算机知识储备】
  • 如何从多个方面进行oracle数据库存储过程优化?
  • 【QNAP威联通NAS系统恢复进阶教程】如果 .conf 和 md9 无法自动组装,如何恢复 NAS?
  • hive 异常任务中间数据清理
  • 数据结构与算法分析——你真的理解查找算法吗——二叉查找树(代码详解)