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

算法训练——day14字母异位词

242. 有效的字母异位词

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

字母异位词。

示例 1:

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

示例 2:

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

提示:

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

进阶: 如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况?


t 是 s 的异位词,等于说:t和s中字符出现的种类和次数相等。

由于字符串只包含小写字母,因此我们可以维护一个长度为 26 的频次数组 ret,先遍历记录字符串 s 中字符出现的频次,然后遍历字符串 t,减去 ret中对应的频次

如果 ret[i]=0,则说明符合条件

//哈希
class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()) return false;
        int []ret = new int [26];
        for(char tmp :s.toCharArray()){
            ret[tmp-'a']++;
        }
        for(char tmp:t.toCharArray()){
            ret[tmp-'a']--;
        }
        for(int tmp:ret){
            if(tmp!=0) return false;
        }
        return true;

    }
}
class Solution {
    public boolean isAnagram(String s, String t) {        
        //排序
        if (s.length() != t.length()) {
            return false;
        }
        char[] Ssort = s.toCharArray();
        char[] tSort = t.toCharArray();
        Arrays.sort(Ssort);
        Arrays.sort(tSort);
        return Arrays.equals(Ssort, tSort);
    }
}
class Solution {
public:
    bool isAnagram(string s, string t) {
        int ret[26] = {0};
        for (int i = 0; i < s.size(); i++) {
            // 求出相对数值
            ret[s[i] - 'a']++;
        }
        for (int i = 0; i < t.size(); i++) {
            ret[t[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (ret[i] != 0) {
                // 如果有元素不为0,说明有不同字母
                return false;
            }
        }
        return true;
    }
};

 

进阶题的思路类似,只是不限制字符数量了。那我们的长度将由s,t来决定,而不是26个字母。

//进阶
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        Map<Character, Integer> ret = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            ret.put(ch, ret.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            ret.put(ch, ret.getOrDefault(ch, 0) - 1);
            if (ret.get(ch) < 0) {
                return false;
            }
        }
        return true;
    }
}

383. 赎金信

给你两个字符串:ransomNote 和 magazine ,判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以,返回 true ;否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1:

输入:ransomNote = "a", magazine = "b"
输出:false

示例 2:

输入:ransomNote = "aa", magazine = "ab"
输出:false

示例 3:

输入:ransomNote = "aa", magazine = "aab"
输出:true

提示:

  • 1 <= ransomNote.length, magazine.length <= 105
  • ransomNote 和 magazine 由小写英文字母组成

思路与异位词一样

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        int[] ret = new int[26];
        for (char c : magazine.toCharArray()) {
            ret[c - 'a']++;
        }
        for (char c : ransomNote.toCharArray()) {
            ret[c - 'a']--;
            if(ret[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        if (ransomNote.size() > magazine.size()) {
            return false;
        }
        vector<int> ret(26);
        for (auto & c : magazine) {
            ret[c - 'a']++;
        }
        for (auto & c : ransomNote) {
            ret[c - 'a']--;
            if (ret[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};


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

相关文章:

  • [vulnhub] DarkHole: 2
  • 【学习笔记】Kylin-Desktop-V10-SP1 麒麟系统知识4——设备设置
  • 《Python 与 SQLite:强大的数据库组合》
  • 每日一题C语言算法题——计算6
  • SparkSql读取数据的方式
  • 【CLIP系列】开篇
  • 计算机三级网络技术总结(二)
  • 【D3.js in Action 3 精译_022】3.2 使用 D3 完成数据准备工作
  • Golang | Leetcode Golang题解之第400题第N位数字
  • 通信工程学习:什么是LCAS链路容量调整机制
  • LLM大模型基础知识学习总结,零基础入门到精通 非常详细收藏我这一篇就够了
  • 1.接口测试基础
  • Selenium等待机制:理解并应用显式等待与隐式等待,解决页面加载慢的问题
  • golang实现正向代理http_proxy和https_proxy
  • 【Python】从基础到进阶(八):文件操作与上下文管理
  • mybatis-generator代码生成
  • iOS 18 新功能:控制中心大變身!控制項目自由選配
  • 手机、平板电脑编程———未来之窗行业应用跨平台架构
  • 「iOS」push与present
  • Centos7安装gitlab-ce(rpm安装方式)
  • 干耳怎么掏耳朵?可视挖耳勺推荐平价
  • DeepFake换脸检测
  • 828华为云征文|基于华为云Flexus云服务器X实现个人博客搭建
  • SpringMVC映射请求;SpringMVC返回值类型;SpringMVC参数绑定;
  • Redis的缓存穿透、缓存雪崩、缓存击穿怎么解决
  • 【苍穹外卖】总结