題目

原文：

Write a method to decide if two strings are anagrams or not.

譯文：

寫一個函數判斷兩個字符串是否是變位詞。

解答

變位詞(anagrams)指的是組成兩個單詞的字符相同，但位置不同的單詞。比如說， abbcd和abcdb就是一對變位詞。該題目有兩種做法：

O(nlogn)的解法

由于組成變位詞的字符是一模一樣的，所以按照字典序排序后，兩個字符串也就相等了。 因此我們可以用O(nlogn)的時間去排序，然后用O(n)的時間比較它們是否相等即可。

代碼如下：

bool isAnagram1(string s, string t){if(s=="" || t=="") return false;if(s.length() != t.length()) return false;sort(&s[0], &s[0]+s.length());sort(&t[0], &t[0]+t.length());if(s == t) return true;else return false; }

O(n)的解法

由于組成變位詞的字符是一模一樣的， 因此我們可以先統計每個字符串中各個字符出現的次數， 然后看這兩個字符串中各字符出現次數是否一樣。如果是，則它們是一對變位詞。 這需要開一個輔助數組來保存各字符的出現次數。我們可以開一個大小是256的整數數組， 遍歷第一個字符串時，將相應字符出現的次數加1；遍歷第二個字符串時， 將相應字符出現的次數減1。最后如果數組中256個數都為0，說明兩個字符串是一對變位詞。 (第1個字符串中出現的字符都被第2個字符串出現的字符抵消了)， 如果數組中有一個不為0，說明它們不是一對變位詞。

代碼如下：

bool isAnagram(string s, string t){if(s=="" || t=="") return false;if(s.length() != t.length()) return false;int len = s.length();int c[256];memset(c, 0, sizeof(c));for(int i=0; i<len; ++i)++c[(int)s[i]];for(int i=0; i<len; ++i)--c[(int)t[i]];for(int i=0; i<256; ++i)if(c[i] != 0)return false;return true; }

?

轉載于:https://www.cnblogs.com/sooner/p/3179940.html

總結

以上是生活随笔為你收集整理的Cracking the coding interview--Q1.4的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。