資訊專(zhuān)欄INFORMATION COLUMN
摘要：排序法復(fù)雜度時(shí)間空間思路因?yàn)樽冃卧~兩個(gè)單詞對(duì)應(yīng)字母出現(xiàn)的次數(shù)都相同，所以如果將兩個(gè)單詞按字母順序排序，肯定會(huì)變?yōu)橐粋€(gè)字符串，如果字符串不相同，則不是變形詞。
Valid Anagram
排序法 復(fù)雜度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.
時(shí)間 O(KlogK) 空間 O(K)
思路因?yàn)樽冃卧~兩個(gè)單詞對(duì)應(yīng)字母出現(xiàn)的次數(shù)都相同，所以如果將兩個(gè)單詞按字母順序排序，肯定會(huì)變?yōu)橐粋€(gè)字符串，如果字符串不相同，則不是變形詞。這里不推薦Java用這個(gè)方法，因?yàn)镴ava得先將字母轉(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));
}
}
哈希表法
復(fù)雜度
時(shí)間 O(K) 空間 O(1)
思路變形詞的本質(zhì)是兩個(gè)單詞中，每個(gè)字母出現(xiàn)的次數(shù)相同，所以我們可以用一個(gè)哈希表，記錄第一個(gè)單詞中每個(gè)字母的個(gè)數(shù)，再遍歷第二個(gè)單詞，減去相應(yīng)的字母出現(xiàn)次數(shù)，如果某個(gè)字母的計(jì)數(shù)器不為0了，則說(shuō)明某個(gè)字母出現(xiàn)的次數(shù)不一樣。這里只用了一個(gè)大小為26的數(shù)組，是假設(shè)只會(huì)出現(xiàn)英文字母。
代碼public class Solution {
public boolean isAnagram(String s, String t) {
int[] table = new int[26];
// 記錄字母在第一個(gè)單詞中出現(xiàn)的次數(shù)
for(int i = 0; i < s.length(); i++){
table[s.charAt(i)-"a"]++;
}
// 減去字母在第二個(gè)單詞中出現(xiàn)的次數(shù)
for(int i = 0; i < t.length(); i++){
table[t.charAt(i)-"a"]--;
}
// 如果某個(gè)計(jì)數(shù)器不為0，則返回假
for(int i = 0; i < 26; i++){
if(table[i]!=0) return false;
}
return true;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64609.html
摘要：統(tǒng)計(jì)字母頻率復(fù)雜度時(shí)間空間思路用一個(gè)位的數(shù)組統(tǒng)計(jì)字符串中每一個(gè)字符出現(xiàn)的次數(shù)，然后同理，維護(hù)一個(gè)長(zhǎng)度為長(zhǎng)度的窗口，來(lái)統(tǒng)計(jì)這個(gè)窗口里母串各個(gè)字符出現(xiàn)的次數(shù)，計(jì)入一個(gè)數(shù)組中。比較這兩個(gè)數(shù)組是否相同就知道是否是變形詞子串了。 Anagram Substring Search Given a text txt[0..n-1] and a pattern pat[0..m-1], write ...
摘要：題目鏈接題目分析判斷給定的兩個(gè)單詞是否同構(gòu)。即，重新排列組合所出現(xiàn)的字母后得到另一個(gè)單詞。思路拆分成數(shù)組后，排序，再拼起來(lái)。最終代碼若覺(jué)得本文章對(duì)你有用，歡迎用愛(ài)發(fā)電資助。 D85 242. Valid Anagram 題目鏈接 242. Valid Anagram 題目分析 判斷給定的兩個(gè)單詞是否同構(gòu)。即，重新排列組合所出現(xiàn)的字母后得到另一個(gè)單詞。 思路 拆分成數(shù)組后，排序，再拼起來(lái)...
摘要：月下半旬攻略道題，目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚(yú)有什么區(qū)別...
摘要：建立一個(gè)長(zhǎng)度為的數(shù)組，統(tǒng)計(jì)所有個(gè)字符在出現(xiàn)的次數(shù)，然后減去這些字符在中出現(xiàn)的次數(shù)。否則，循環(huán)結(jié)束，說(shuō)明所有字符在和中出現(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....
摘要：我們將每個(gè)詞排序后，根據(jù)這個(gè)鍵值，找到哈希表中相應(yīng)的列表，并添加進(jìn)去。 Group Anagrams 最新更新請(qǐng)見(jiàn)：https://yanjia.me/zh/2019/01/... Given an array of strings, group anagrams together. For example, given: [eat, tea, tan, ate, nat, bat...
閱讀 3494·2023-04-25 21:43
閱讀 3106·2019-08-29 17:04
閱讀 807·2019-08-29 16:32
閱讀 1546·2019-08-29 15:16
閱讀 2158·2019-08-29 14:09
閱讀 2747·2019-08-29 13:07
閱讀 1633·2019-08-26 13:32
閱讀 1326·2019-08-26 12:00
