[Leetcode] Valid Anagram 驗證變形詞

justjavac 發布于2019-08-14 12:38 / 2880人閱讀

摘要：排序法復雜度時間空間思路因為變形詞兩個單詞對應字母出現的次數都相同，所以如果將兩個單詞按字母順序排序，肯定會變為一個字符串，如果字符串不相同，則不是變形詞。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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