发现两个词是否是彼此的字谜

Question

我正在寻找一种方法来查找两个字符串是否是彼此的字谜.

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

我提出的解决方案是为了对两个字符串进行排序并比较两个字符串中的每个字符直到任一字符串的结尾.它将是O(logn).我正在寻找一些其他有效的方法,它不会改变比较2个字符串

Answer 1

计算两个字符串中每个字符的频率.检查两个直方图是否匹配.O(n)时间,O(1)空间(假设ASCII)(当然它仍然是Unicode的O(1)空间但是表格会变得非常大).

Answer 2

获取素数表,足以将每个素数映射到每个字符.所以从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 3

1. 创建一个Hashmap,其中键 - 字母和值 - 字母的频率,
2. for first string填充hashmap(O(n))
3. for second string decrement count并从hashmap O(n)中删除元素
4. 如果hashmap为空,则字符串是anagram,否则不是.

Answer 4

步骤是:

1. 检查两个单词/字符串的长度是否相等然后只检查anagram否则什么都不做
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");
        }
    }
}