查找兩個單詞是否是對方的字典

Question

我正在尋找一種方法來查找兩個字符串是否是另一個的字符串。

Ex: string1 - abcde 
string2 - abced 
Ans = true 
Ex: string1 - abcde 
string2 - abcfed 
Ans = false 

，我想出了這樣的是兩個字符串進行排序和每個字符由兩個字符串，直到要麼strings.It年底比較，將是O（LOGN）。我要尋找一些其他有效的解決方案被比較

Answer 1

計算兩個字符串中每個字符的頻率。檢查兩個直方圖是否匹配。 O（n）時間，O（1）空間（假設ASCII）（當然它仍然是O（1）空間的Unicode，但表格將變得非常大）。

Answer 2

1. 創建一個HashMap其中鍵不改變2串方法 -​​ 字母和值 - 信frequencey，
2. 爲第一串填充的散列映射（O（N））
3. 爲第二個字符串遞減計數並從hashmap O中移除元素（n）
4. 如果散列表爲空，則該字符串不是字符串。

Answer 3

那麼你大概可以通過首先檢查長度，然後對數字進行快速校驗和來改進最好的情況和平均情況（不是複雜的，因爲這可能會比排序更糟糕，序數值的總和），然後進行排序，然後進行比較。

如果字符串非常短，校驗和開銷與許多語言的排序沒有太大差異。

Answer 4

我想你的排序算法不是真的O（log n），是嗎？

您可以得到的最好的是O（n）爲您的算法，因爲您必須檢查每個字符。

您可以使用兩個表來存儲每個字中每個字母的計數，用O（n）填充並與O（1）比較。

Answer 5

獲取素數表格，足以將每個素數映射到每個字符。因此，從1開始，通過線，乘以代表當前字符的素數。你得到的數字只取決於字符串中的字符，而不取決於它們的順序，並且每一組唯一的字符對應於唯一的數字，因爲任何數字都可以用一種方式來分解。所以你可以比較兩個數字來說明一個字符串是否是對方的字典。

不幸的是，你必須使用多個精度（任意精度）的整數算術來做到這一點，否則當你使用這種方法時你會得到溢出或舍入異常。
爲此，您可以使用庫如BigInteger,GMP, MPIR或IntX。

僞代碼：

prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101} 

primehash(string) 
    Y = 1; 
    foreach character in string 
     Y = Y * prime[character-'a'] 

    return Y 

isanagram(str1, str2) 
    return primehash(str1)==primehash(str2) 

Answer 6

這個怎麼樣？

 
a = "lai d" 
b = "di al" 
sorteda = [] 
sortedb = [] 
for i in a: 
    if i != " ": 
     sorteda.append(i) 
     if c == len(b): 
      for x in b: 
       c -= 1 
       if x != " ": 
        sortedb.append(x) 
sorteda.sort(key = str.lower) 
sortedb.sort(key = str.lower) 

print sortedb 
print sorteda 

print sortedb == sorteda 

Answer 7

看來下面的實現也可以檢查嗎？

int histogram[256] = {0}; 
for (int i = 0; i < strlen(str1); ++i) { 
    /* Just inc and dec every char count and 
    * check the histogram against 0 in the 2nd loop */ 
    ++histo[str1[i]]; 
    --histo[str2[i]]; 
} 

for (int i = 0; i < 256; ++i) { 
    if (histo[i] != 0) 
    return 0; /* not an anagram */ 
} 

return 1; /* an anagram */ 

Answer 8

的步驟是：

1. 檢查的兩個單詞/字符串的長度是否相等，然後才能進行檢查字謎別的什麼也不做
2. 排序兩個單詞/字符串然後比較

Java代碼是相同的：

/* 
* To change this template, choose Tools | Templates 
* and open the template in the editor. 
*/ 
package anagram; 

import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.Arrays; 

/** 
* 
* @author Sunshine 
*/ 
public class Anagram { 

    /** 
    * @param args the command line arguments 
    */ 
    public static void main(String[] args) throws IOException { 
     // TODO code application logic here 
     System.out.println("Enter the first string"); 
     BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
     String s1 = br.readLine().toLowerCase(); 
     System.out.println("Enter the Second string"); 
     BufferedReader br2 = new BufferedReader(new InputStreamReader(System.in)); 
     String s2 = br2.readLine().toLowerCase(); 
     char c1[] = null; 
     char c2[] = null; 
     if (s1.length() == s2.length()) { 


      c1 = s1.toCharArray(); 
      c2 = s2.toCharArray(); 

      Arrays.sort(c1); 
      Arrays.sort(c2); 

      if (Arrays.equals(c1, c2)) { 
       System.out.println("Both strings are equal and hence they have anagram"); 
      } else { 
       System.out.println("Sorry No anagram in the strings entred"); 
      } 

     } else { 
      System.out.println("Sorry the string do not have anagram"); 
     } 
    } 
} 

Answer 9

Xor'ing這兩個弦如何？這肯定會爲O（n）的

char* arr1="ab cde"; 
int n1=strlen(arr1); 
char* arr2="edcb a"; 
int n2=strlen(arr2); 
// to check for anagram; 
int c=0; 
int i=0, j=0; 
if(n1!=n2) 
    printf("\nNot anagram"); 
else { 
    while(i<n1 || j<n2) 
    { 
     c^= ((int)arr1[i]^(int)arr2[j]); 
     i++; 
     j++; 
    } 
} 

if(c==0) { 
    printf("\nAnagram"); 
} 
else printf("\nNot anagram"); 

}

Answer 10

/* Program to find the strings are anagram or not*/ 
/* Author Senthilkumar M*/ 

Eg. 
    Anagram: 
    str1 = stackoverflow 
    str2 = overflowstack 

    Not anagram:`enter code here` 
    str1 = stackforflow 
    str2 = stacknotflow 

int is_anagram(char *str1, char *str2) 
{ 
     int l1 = strlen(str1); 
     int l2 = strlen(str2); 
     int s1 = 0, s2 = 0; 
     int i = 0; 

     /* if both the string are not equal it is not anagram*/ 
     if(l1 != l2) { 
       return 0; 
     } 
     /* sum up the character in the strings 
      if the total sum of the two strings is not equal 
      it is not anagram */ 
     for(i = 0; i < l1; i++) { 
       s1 += str1[i]; 
       s2 += str2[i]; 
     } 
     if(s1 != s2) { 
       return 0; 
     } 
     return 1; 
} 

Answer 11

C＃

public static bool AreAnagrams(string s1, string s2) 
{ 
    if (s1 == null) throw new ArgumentNullException("s1"); 
    if (s2 == null) throw new ArgumentNullException("s2"); 

    var chars = new Dictionary<char, int>(); 
    foreach (char c in s1) 
    { 
     if (!chars.ContainsKey(c)) 
      chars[c] = 0; 
     chars[c]++; 
    } 
    foreach (char c in s2) 
    { 
     if (!chars.ContainsKey(c)) 
      return false; 
     chars[c]--; 
    } 

    return chars.Values.All(i => i == 0); 
} 

一些測試：

[TestMethod] 
public void TestAnagrams() 
{ 
    Assert.IsTrue(StringUtil.AreAnagrams("anagramm", "nagaramm")); 
    Assert.IsTrue(StringUtil.AreAnagrams("anzagramm", "nagarzamm")); 
    Assert.IsTrue(StringUtil.AreAnagrams("anz121agramm", "nag12arz1amm")); 
    Assert.IsFalse(StringUtil.AreAnagrams("anagram", "nagaramm")); 
    Assert.IsFalse(StringUtil.AreAnagrams("nzagramm", "nagarzamm")); 
    Assert.IsFalse(StringUtil.AreAnagrams("anzagramm", "nag12arz1amm")); 
} 

Answer 12

在Java中，我們也可以像這和它的非常簡單的邏輯

import java.util.*; 

class Anagram 
{ 
public static void main(String args[]) throws Exception 
{ 
    Boolean FLAG=true; 

    Scanner sc= new Scanner(System.in); 

    System.out.println("Enter 1st string"); 

    String s1=sc.nextLine(); 

    System.out.println("Enter 2nd string"); 

    String s2=sc.nextLine(); 

    int i,j; 
    i=s1.length(); 
    j=s2.length(); 

    if(i==j) 
    { 
    for(int k=0;k<i;k++) 
    { 
    for(int l=0;l<i;l++) 
    { 
    if(s1.charAt(k)==s2.charAt(l)) 
    { 
     FLAG=true; 
     break; 
    } 
    else 
    FLAG=false; 
    } 
    } 
    } 
    else 
    FLAG=false; 
    if(FLAG) 
    System.out.println("Given Strings are anagrams"); 
    else 
    System.out.println("Given Strings are not anagrams"); 
} 
} 

Answer 13

如果兩個字符串的長度相等，那麼繼續，如果不是，則字符串不是字母。

迭加每個字符串時，總結每個字符的序號。如果和數相等，那麼這些字符串就是anagrams。

實施例：

public Boolean AreAnagrams(String inOne, String inTwo) { 

     bool result = false; 

     if(inOne.Length == inTwo.Length) { 

      int sumOne = 0; 
      int sumTwo = 0; 

      for(int i = 0; i < inOne.Length; i++) { 

       sumOne += (int)inOne[i]; 
       sumTwo += (int)inTwo[i]; 
      } 

      result = sumOne == sumTwo; 
     } 

     return result; 
    } 

Answer 14

對於已知（小）組有效字母（例如ASCII）的使用表具有與每個有效信相關聯的計數。第一個字符串遞增計數，第二個字符串遞減計數。最後遍歷整個表，看看所有計數是否爲零（字符串是anagrams）還是非零值（字符串不是字母）。確保將所有字符轉換爲大寫（或小寫，完全相同）並忽略空格。

對於大量有效字母（如Unicode），請勿使用表格，而應使用散列表。它有O（1）次添加，查詢和刪除和O（n）空間。第一個字符串遞增計數的字母，第二個字符串遞減計數的字母。從哈希表中刪除成爲零的計數。如果末尾散列表爲空，則字符串是anagrams。或者，只要任何計數變爲負數，搜索就會以負面結果終止。

這裏是C＃的詳細解釋和執行：Testing If Two Strings are Anagrams

Answer 15

如何轉換成字符的int值和總結：

如果和的值都等於那麼他們字謎每個其他。

def are_anagram1(s1, s2): 
    return [False, True][sum([ord(x) for x in s1]) == sum([ord(x) for x in s2])] 

s1 = 'james' 
s2 = 'amesj' 
print are_anagram1(s1,s2) 

該解決方案僅適用於'A'到'Z'和'a'到'z'。

Answer 16

static bool IsAnagram(string s1, string s2) 
     { 

      if (s1.Length != s2.Length) 
       return false; 
      else 
      { 
       int sum1 = 0; 
       for (int i = 0; i < s1.Length; i++) 
       sum1 += (int)s1[i]-(int)s2[i]; 
       if (sum1 == 0) 
        return true; 
       else 
        return false; 
      } 
     } 

Answer 17

代碼找到兩個詞是否字謎：

邏輯在幾個答案已經解釋和幾個要求的代碼。該解決方案在O（n）時間內產生結果。

此方法計算每個字符出現的次數並將其存儲在每個字符串的相應ASCII位置中。然後比較兩個數組的數量。如果不相等，給定的字符串不是字謎。

public boolean isAnagram(String str1, String str2) 
{ 
    //To get the no of occurrences of each character and store it in their ASCII location 
    int[] strCountArr1=getASCIICountArr(str1); 
    int[] strCountArr2=getASCIICountArr(str2); 

    //To Test whether the two arrays have the same count of characters. Array size 256 since ASCII 256 unique values 
    for(int i=0;i<256;i++) 
    { 
     if(strCountArr1[i]!=strCountArr2[i]) 
      return false; 
    } 
    return true; 
} 

public int[] getASCIICountArr(String str) 
{ 
    char c; 
    //Array size 256 for ASCII 
    int[] strCountArr=new int[256]; 
    for(int i=0;i<str.length();i++) 
    { 
     c=str.charAt(i); 
     c=Character.toUpperCase(c);// If both the cases are considered to be the same 
     strCountArr[(int)c]++; //To increment the count in the character's ASCII location 
    } 
    return strCountArr; 
} 

Answer 18

使用ASCII哈希映射，該哈希映射允許對每個字符進行O（1）查找。

上面列出的java示例正在轉換爲似乎不完整的小寫字母。我在C的例子，簡單地初始化散列映射陣列ASCII values到「-1」

如果字符串2的長度比串1不同，沒有字謎

否則，我們更新相應的散列映射對於字符串1和字符串2中的每個字符，值爲0

然後對於字符串1中的每個字符，我們更新哈希映射中的計數。類似地，我們遞減string2中每個字符的計數值。

如果每個字符都是字母，結果應該將值設置爲0。如果沒有，通過字符串1設置了一些積極的值保持

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

#define ARRAYMAX 128 

#define True  1 
#define False  0 

int isAnagram(const char *string1, 
      const char *string2) { 

    int str1len = strlen(string1); 
    int str2len = strlen(string2); 

    if (str1len != str2len) /* Simple string length test */ 
     return False; 

    int * ascii_hashtbl = (int *) malloc((sizeof(int) * ARRAYMAX)); 
    if (ascii_hashtbl == NULL) { 
     fprintf(stderr, "Memory allocation failed\n"); 
     return -1; 
    } 
    memset((void *)ascii_hashtbl, -1, sizeof(int) * ARRAYMAX); 
    int index = 0; 
    while (index < str1len) { /* Populate hash_table for each ASCII value 
           in string1*/ 
     ascii_hashtbl[(int)string1[index]] = 0; 
     ascii_hashtbl[(int)string2[index]] = 0; 
     index++; 
    } 
    index = index - 1; 
    while (index >= 0) { 
     ascii_hashtbl[(int)string1[index]]++; /* Increment something */ 
     ascii_hashtbl[(int)string2[index]]--; /* Decrement something */ 
     index--; 
    } 
    /* Use hash_table to compare string2 */ 
    index = 0; 
    while (index < str1len) { 
     if (ascii_hashtbl[(int)string1[index]] != 0) { 
      /* some char is missing in string2 from string1 */ 
      free(ascii_hashtbl); 
      ascii_hashtbl = NULL; 
      return False; 
     } 
     index++; 
    } 
    free(ascii_hashtbl); 
    ascii_hashtbl = NULL; 
    return True; 
} 

int main() { 
    char array1[ARRAYMAX], array2[ARRAYMAX]; 
    int flag; 

    printf("Enter the string\n"); 
    fgets(array1, ARRAYMAX, stdin); 
    printf("Enter another string\n"); 
    fgets(array2, ARRAYMAX, stdin); 

    array1[strcspn(array1, "\r\n")] = 0; 
    array2[strcspn(array2, "\r\n")] = 0; 
    flag = isAnagram(array1, array2); 
    if (flag == 1) 
     printf("%s and %s are anagrams.\n", array1, array2); 
    else if (flag == 0) 
     printf("%s and %s are not anagrams.\n", array1, array2); 

    return 0; 
} 

Answer 19

如果字符串只有ASCII字符：

1. 創建256長度
2. 陣列橫動陣列中的第一串和增量計數器index =字符的ascii值。當您到達字符串末尾時，還要繼續計算字符以查找長度
3. 遍歷字符的index = ascii值處的第二個字符串並遞減數組中的計數器。如果在遞減前該值爲0，則返回false，因爲字符串不是字母。還要跟蹤第二個字符串的長度。
4. 在字符串遍歷結束時，如果兩者的長度相等，則返回true，否則返回false。

如果字符串可以有unicode字符，則使用哈希映射而不是數組來跟蹤頻率。算法的其餘部分保持不變。

注：

1. 計算長度，同時增加字符列陣確保我們遍歷每個串一次。
2. 僅在ASCII字符串的情況下使用數組根據需求優化空間。

Answer 20

實施斯威夫特3：

func areAnagrams(_ str1: String, _ str2: String) -> Bool { 
    return dictionaryMap(forString: str1) == dictionaryMap(forString: str2) 
} 

func dictionaryMap(forString str: String) -> [String : Int] { 
    var dict : [String : Int] = [:] 
    for var i in 0..<str.characters.count { 
     if let count = dict[str[i]] { 
      dict[str[i]] = count + 1 
     }else { 
      dict[str[i]] = 1 
     } 
    }   
    return dict 
} 
//To easily subscript characters 
extension String { 
    subscript(i: Int) -> String { 
     return String(self[index(startIndex, offsetBy: i)]) 
    } 
} 

Answer 21

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.LinkedHashMap; 
import java.util.Map; 
import java.util.Scanner; 

/** 
* -------------------------------------------------------------------------- 
* Finding Anagrams in the given dictionary. Anagrams are words that can be 
* formed from other words Ex :The word "words" can be formed using the word 
* "sword" 
* -------------------------------------------------------------------------- 
* Input : if choose option 2 first enter no of word want to compare second 
* enter word ex: 
* 
* Enter choice : 1:To use Test Cases 2: To give input 2 Enter the number of 
* words in dictionary 
* 6 
* viq 
* khan 
* zee 
* khan 
* am 
*  
* Dictionary : [ viq khan zee khan am] 
* Anagrams 1:[khan, khan] 
* 
*/ 
public class Anagrams { 

    public static void main(String args[]) { 
     // User Input or just use the testCases 
     int choice; 
     @SuppressWarnings("resource") 
     Scanner scan = new Scanner(System.in); 
     System.out.println("Enter choice : \n1:To use Test Cases 2: To give input"); 
     choice = scan.nextInt(); 
     switch (choice) { 
     case 1: 
      testCaseRunner(); 
      break; 
     case 2: 
      userInput(); 
     default: 
      break; 
     } 
    } 

    private static void userInput() { 
     @SuppressWarnings("resource") 
     Scanner scan = new Scanner(System.in); 
     System.out.println("Enter the number of words in dictionary"); 
     int number = scan.nextInt(); 
     String dictionary[] = new String[number]; 
     // 
     for (int i = 0; i < number; i++) { 
      dictionary[i] = scan.nextLine(); 
     } 
     printAnagramsIn(dictionary); 

    } 

    /** 
    * provides a some number of dictionary of words 
    */ 
    private static void testCaseRunner() { 

     String dictionary[][] = { { "abc", "cde", "asfs", "cba", "edcs", "name" }, 
       { "name", "mane", "string", "trings", "embe" } }; 
     for (int i = 0; i < dictionary.length; i++) { 
      printAnagramsIn(dictionary[i]); 
     } 
    } 

    /** 
    * Prints the set of anagrams found the give dictionary 
    * 
    * logic is sorting the characters in the given word and hashing them to the 
    * word. Data Structure: Hash[sortedChars] = word 
    */ 
    private static void printAnagramsIn(String[] dictionary) { 
     System.out.print("Dictionary : [");// + dictionary); 
     for (String each : dictionary) { 
      System.out.print(each + " "); 
     } 
     System.out.println("]"); 
     // 

     Map<String, ArrayList<String>> map = new LinkedHashMap<String, ArrayList<String>>(); 
     // review comment: naming convention: dictionary contains 'word' not 
     // 'each' 
     for (String each : dictionary) { 
      char[] sortedWord = each.toCharArray(); 
      // sort dic value 
      Arrays.sort(sortedWord); 
      //input word 
      String sortedString = new String(sortedWord); 
      // 
      ArrayList<String> list = new ArrayList<String>(); 
      if (map.keySet().contains(sortedString)) { 
       list = map.get(sortedString); 
      } 
      list.add(each); 
      map.put(sortedString, list); 
     } 
     // print anagram 
     int i = 1; 
     for (String each : map.keySet()) { 
      if (map.get(each).size() != 1) { 
       System.out.println("Anagrams " + i + ":" + map.get(each)); 
       i++; 
      } 
     } 
    } 
}