查找两个单词是否是对方的字典

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++; 
      } 
     } 
    } 
}