发现两个单词是否是对方的字典
我正在寻找一种方法来查找两个string是否是另一个string。
Ex: string1 - abcde string2 - abced Ans = true Ex: string1 - abcde string2 - abcfed Ans = false 我想出的解决scheme是sorting两个string，并比较每个字符从两个string，直到任何string的结尾。这将是O（logn）。我正在寻找其他有效的方法，不会改变2个string进行比较
计算两个string中每个字符的频率。 检查两个直方图是否匹配。 O（n）时间，O（1）空间（假设为ASCII）（当然对Unicode仍然是O（1）空间，但是表格会变得非常大）。
获取素数表格，足以将每个素数映射到每个字符。 所以从1开始，通过行，乘以代表当前字符的素数。 你得到的数字只取决于string中的字符，而不取决于它们的顺序，每一组唯一的字符对应于唯一的数字，因为任何数字都可以用一种方式来分解。 所以你可以比较两个数字来表示一个string是否是对方的字典。
不幸的是，你必须使用多个精度（任意精度）的整数algorithm来做到这一点，否则当使用这种方法时，你会得到溢出或四舍五入的exception。
为此，您可以使用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)
- 创build一个HashMap，其中的字母和数字的字母，
- 为第一个string填充hashmap（O（n））
- 对于第二个string递减计数并从哈希映射中移除元素O（n）
- 如果hashmap为空，则该string是anagram否则不是。
步骤是：
- 检查两个单词/string的长度是否相等，然后只检查string，否则什么也不做
- sorting两个单词/string，然后比较
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"); } } }
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); }
一些testing：
[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")); }
代码来查找两个单词是否是字谜：
逻辑已经解释了几个答案，很less要求代码。 该解决scheme在O（n）时间内产生结果。
这种方法计算每个字符的出现次数，并将其存储在每个string的相应ASCII位置中。 然后比较两个数组的数量。 如果不相等，给定的string不是字谜。
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; }
使用一个ASCII哈希映射，允许O（1）查找每个字符。
上面列出的Java示例正在转换为似乎不完整的小写字母。 我有一个C的例子，简单地初始化一个哈希映射数组的ASCII值为 '-1'
如果string2的长度与string1的长度不同，则不需要字符
否则，我们为string1和string2中的每个字符更新适当的散列映射值为0
然后，对于string1中的每个字符，我们更新散列图中的计数。 类似地，我们递减string2中每个字符的计数值。
如果每个字符都是字符，结果应该将值设置为0。 如果不是，由string1设置的一些正值仍然存在
#include <stdio.h> #include <stdlib.h> #include <string.h> #define ARRAYMAX 128 #define True 1 #define False 0 #define Infinity -1 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 = 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[100], array2[100]; int flag; printf("Enter the string\n"); gets(array1); printf("Enter another string\n"); gets(array2); 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; }
那么你大概可以通过首先检查长度，然后对数字进行快速校验和（不是复杂的，因为这可能是比sorting更糟糕的顺序，只是序数值的总和），可以改善最好的情况和平均情况。然后sorting，然后比较。
如果string非常短，那么校验和的开销与许多语言的sorting没有太大的差别。
这个怎么样？
a =“lai d”
b =“di al”
sorteda = []
sortedb = []
因为我在一个：
如果我！=“”：
sorteda.append（ⅰ）
如果c == len（b）：
for x in b：
c - = 1
如果x！=“”：
sortedb.append（x）的
sorteda.sort（key = str.lower）
sortedb.sort（key = str.lower）
打印sortedb
打印sorting
打印sortedb ==sorting
如何对两个string进行操作？ 这肯定是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");
}
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; } }
对于已知的（和小的）有效字母集（例如ASCII），使用与每个有效字母相关的计数表。 第一个string递增计数，第二个string递减计数。 最后遍历表，看看是否所有计数都是零（string是字母）或有非零值（string不是字母）。 确保将所有字符转换为大写（或小写，完全相同）并忽略空格。
对于大量有效字母（如Unicode），请不要使用表格，而应使用散列表。 它有O（1）时间添加，查询和删除和O（n）空间。 来自第一个string递增计数的字母，第二个string递减计数的字母。 从哈希表中删除成为零的计数。 如果结尾的散列表是空的，则string是字符。 或者，只要任何计数变为负数，search就会以负面结果终止。
下面是C＃中详细的解释和实现： testing如果两个string是Anagrams
如果string只有ASCII字符：
- 创build一个长度为256的数组
- 遍历字符的index = ascii值的第一个string并在数组中增加计数器。 当你到达string的结尾时，还要继续计算字符长度
- 遍历第二个string，并在字符的index = ascii值处递减数组中的计数器。 如果在递减之前该值是0，则返回false，因为string不是字母。 还要跟踪第二个string的长度。
- 在string遍历结束时，如果两者的长度相等，则返回true，否则返回false。
如果string可以具有Unicode字符，则使用哈希映射而不是数组来跟踪频率。 其余的algorithm保持不变。
笔记：
- 在向数组添加字符时计算长度确保我们只遍历每个string一次。
- 在仅使用ASCII的string的情况下使用数组根据需要优化空间。
我猜你的sortingalgorithm不是真的O（log n），是吗？
你可以得到最好的是你的algorithmO（n），因为你必须检查每个字符。
您可以使用两个表格来存储每个字中每个字母的计数，用O（n）填充并与O（1）比较。
看来下面的实现也是可以的，你能检查吗？
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 */
/* 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; }
如果两个string的长度相等，则不然则string不是字符。
在总结每个字符的序号的同时迭代每个string。 如果总和相等，那么这些string就是字谜。
例：
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; }
在Swift 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)]) } }
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++; } } } }
在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"); } }
如何转换成字符的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)
此解决scheme仅适用于“A”到“Z”和“a”到“z”。
