成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

[Leetcode] Valid Anagram 驗證變形詞

justjavac / 2948人閱讀

摘要：排序法復雜度時間空間思路因為變形詞兩個單詞對應字母出現(xiàn)的次數(shù)都相同，所以如果將兩個單詞按字母順序排序，肯定會變?yōu)橐粋€字符串，如果字符串不相同，則不是變形詞。

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)

思路

因為變形詞兩個單詞對應字母出現(xiàn)的次數(shù)都相同，所以如果將兩個單詞按字母順序排序，肯定會變?yōu)橐粋€字符串，如果字符串不相同，則不是變形詞。這里不推薦Java用這個方法，因為Java得先將字母轉(zhuǎn)化為char數(shù)組再排序。

代碼 
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)

思路

變形詞的本質(zhì)是兩個單詞中，每個字母出現(xiàn)的次數(shù)相同，所以我們可以用一個哈希表，記錄第一個單詞中每個字母的個數(shù)，再遍歷第二個單詞，減去相應的字母出現(xiàn)次數(shù)，如果某個字母的計數(shù)器不為0了，則說明某個字母出現(xiàn)的次數(shù)不一樣。這里只用了一個大小為26的數(shù)組，是假設只會出現(xiàn)英文字母。

代碼 
public class Solution {
    public boolean isAnagram(String s, String t) {
        int[] table = new int[26];
        // 記錄字母在第一個單詞中出現(xiàn)的次數(shù)
        for(int i = 0; i < s.length(); i++){
            table[s.charAt(i)-"a"]++;
        }
        // 減去字母在第二個單詞中出現(xiàn)的次數(shù)
        for(int i = 0; i < t.length(); i++){
            table[t.charAt(i)-"a"]--;
        }
        // 如果某個計數(shù)器不為0，則返回假
        for(int i = 0; i < 26; i++){
            if(table[i]!=0) return false;
        }
        return true;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/64609.html

相關(guān)文章

  • [Algo] Anagram Substring Search 變形詞子串

    摘要：統(tǒng)計字母頻率復雜度時間空間思路用一個位的數(shù)組統(tǒng)計字符串中每一個字符出現(xiàn)的次數(shù)，然后同理，維護一個長度為長度的窗口，來統(tǒng)計這個窗口里母串各個字符出現(xiàn)的次數(shù)，計入一個數(shù)組中。比較這兩個數(shù)組是否相同就知道是否是變形詞子串了。 Anagram Substring Search Given a text txt[0..n-1] and a pattern pat[0..m-1], write ...

    Channe 評論0 收藏0

  • Leetcode PHP題解--D85 242. Valid Anagram

    摘要：題目鏈接題目分析判斷給定的兩個單詞是否同構(gòu)。即，重新排列組合所出現(xiàn)的字母后得到另一個單詞。思路拆分成數(shù)組后，排序，再拼起來。最終代碼若覺得本文章對你有用，歡迎用愛發(fā)電資助。 D85 242. Valid Anagram 題目鏈接 242. Valid Anagram 題目分析 判斷給定的兩個單詞是否同構(gòu)。即，重新排列組合所出現(xiàn)的字母后得到另一個單詞。 思路 拆分成數(shù)組后，排序，再拼起來...

    zgbgx 評論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

    摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...

    tain335 評論0 收藏0

  • [LintCode/LeetCode] Two Strings are Anagrams/Valid

    摘要：建立一個長度為的數(shù)組，統(tǒng)計所有個字符在出現(xiàn)的次數(shù)，然后減去這些字符在中出現(xiàn)的次數(shù)。否則，循環(huán)結(jié)束，說明所有字符在和中出現(xiàn)的次數(shù)一致，返回。 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 評論0 收藏0

  • [Leetcode] Group Anagrams 變形詞

    摘要：我們將每個詞排序后，根據(jù)這個鍵值，找到哈希表中相應的列表，并添加進去。 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 評論0 收藏0

發(fā)表評論

0條評論

閱讀需要支付1元查看
<