[Leetcode] Valid Anagram 验证变形词

justjavac 发布于2019-08-14 12:38 / 2802人阅读

摘要：排序法复杂度时间空间思路因为变形词两个单词对应字母出现的次数都相同，所以如果将两个单词按字母顺序排序，肯定会变为一个字符串，如果字符串不相同，则不是变形词。

Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.
For example, s = "anagram", t = "nagaram", return true. s = "rat", t = "car", return false.
Note: You may assume the string contains only lowercase alphabets.

排序法 复杂度

时间 O(KlogK) 空间 O(K)

思路

因为变形词两个单词对应字母出现的次数都相同，所以如果将两个单词按字母顺序排序，肯定会变为一个字符串，如果字符串不相同，则不是变形词。这里不推荐Java用这个方法，因为Java得先将字母转化为char数组再排序。

代码

public class Solution {
    public boolean isAnagram(String s, String t) {
        char[] word1 = s.toCharArray();
        char[] word2 = t.toCharArray();
        Arrays.sort(word1);
        Arrays.sort(word2);
        return String.valueOf(word1).equals(String.valueOf(word2));
    }
}

哈希表法 复杂度

时间 O(K) 空间 O(1)

思路

变形词的本质是两个单词中，每个字母出现的次数相同，所以我们可以用一个哈希表，记录第一个单词中每个字母的个数，再遍历第二个单词，减去相应的字母出现次数，如果某个字母的计数器不为0了，则说明某个字母出现的次数不一样。这里只用了一个大小为26的数组，是假设只会出现英文字母。

代码

public class Solution {
    public boolean isAnagram(String s, String t) {
        int[] table = new int[26];
        // 记录字母在第一个单词中出现的次数
        for(int i = 0; i < s.length(); i++){
            table[s.charAt(i)-"a"]++;
        }
        // 减去字母在第二个单词中出现的次数
        for(int i = 0; i < t.length(); i++){
            table[t.charAt(i)-"a"]--;
        }
        // 如果某个计数器不为0，则返回假
        for(int i = 0; i < 26; i++){
            if(table[i]!=0) return false;
        }
        return true;
    }
}

云服务器 GPU云服务器 Anagram LeetCode Valid valid?file

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64609.html

[Algo] Anagram Substring Search 变形词子串

摘要：统计字母频率复杂度时间空间思路用一个位的数组统计字符串中每一个字符出现的次数，然后同理，维护一个长度为长度的窗口，来统计这个窗口里母串各个字符出现的次数，计入一个数组中。比较这两个数组是否相同就知道是否是变形词子串了。 Anagram Substring Search Given a text txt[0..n-1] and a pattern pat[0..m-1], write ...

Channe 2019-08-14 12:45 评论0 收藏0
Leetcode PHP题解--D85 242. Valid Anagram

摘要：题目链接题目分析判断给定的两个单词是否同构。即，重新排列组合所出现的字母后得到另一个单词。思路拆分成数组后，排序，再拼起来。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D85 242. Valid Anagram 题目链接 242. Valid Anagram 题目分析判断给定的两个单词是否同构。即，重新排列组合所出现的字母后得到另一个单词。思路拆分成数组后，排序，再拼起来...

zgbgx 2019-07-01 13:57 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
[LintCode/LeetCode] Two Strings are Anagrams/Valid

摘要：建立一个长度为的数组，统计所有个字符在出现的次数，然后减去这些字符在中出现的次数。否则，循环结束，说明所有字符在和中出现的次数一致，返回。 Program Write a method anagram(s,t) to decide if two strings are anagrams or not. Example Given s=abcd, t=dcab, return true....

vslam 2019-08-14 15:22 评论0 收藏0
[Leetcode] Group Anagrams 变形词

摘要：我们将每个词排序后，根据这个键值，找到哈希表中相应的列表，并添加进去。 Group Anagrams 最新更新请见：https://yanjia.me/zh/2019/01/... Given an array of strings, group anagrams together. For example, given: [eat, tea, tan, ate, nat, bat...

Lin_YT 2019-08-14 12:29 评论0 收藏0