算法题：比较字符串是否相等

Question

字符串相等的条件：
1、不区分大小写
2、不区分顺序
比如“aBc”=“ABC”
“abc”=“bac”要求：要有自己的算法思想。======
一个方法：
1、先把两个字符串都转化为大写或小写
2、把字符串转化为char数组，然后使用冒泡或比较或其他排序算法实现排序
3、使用equals来判断排序后的连个字符串是否相等这个方法可行，但是没有体现出做题人自己的算法思想，用的都是系统自带的实现功能。怎么使用自己的算法来实现这个功能？

Answer 1

不知道用哈希集合怎么实现。用HashSet吗？同时还要考虑abcabc和abcaba是不相等的。能否说的详细一点？

Answer 2

public static boolean equels(String first , String second ) {
first = first.toLowerCase() ;
second = second.toLowerCase() ;

byte[] ch = first.getBytes() ;
byte[] ch1 = second.getBytes() ;
sort(ch);
sort(ch1);

return  new String(ch).equals(new String(ch1));
}
private static void sort(byte[] ch) {
for(int i=0 ; i<ch.length-1 ; i++) {
int lag = ch[i];
int index = i ;
for(int j=i+1 ; j<ch.length ; j++) {
if(lag < ch[j]) {
lag = ch[j];
index = j ;
}
}
ch[index] = ch[i];
ch[i] = (byte) lag ;
}
}不知合意否？

Answer 3

/**
 * 思路
 * 1.比较长度
 * 2.source转换char数组，去desc匹配，然后删除。
 * @param source
 * @param desc
 * @throws Exception
 */
public static void checkString(String source, String desc) throws Exception {
if (source.length() != desc.length()) {
System.out.println("not equal!");
return;
}
source = source.toLowerCase();
desc = desc.toLowerCase();
char[] sourceChars = source.toCharArray();
for (char sourceChar : sourceChars) {
int index = desc.indexOf(sourceChar);
//不匹配视为不相等
if (index > -1) {
desc = desc.substring(0, index)
+ desc.substring(index + 1, desc.length());
} else {
System.out.println("not equal");
return;
}
}
System.out.println("equal");
}
简单实现而已

Answer 4

我不知道这个算不算最好的，当时我也想到这点，但是没有想到要删除，结果可能造成abcb与abca被判断相等。

Answer 5

参考HashSet的哈希算法。    public static int getHashCode(String str){
int h=0;
for(Character c:str.toUpperCase().toCharArray()){
    h+=c.hashCode();
}
return h;
    }
    public static void main(String[]args)
    {
System.out.println(getHashCode("abc")==getHashCode("aca"));
    }

Answer 6

这个算法不严谨，HASHCODE的规则是：
1、HASHCODE不等时，两值一定不等；
2、HASHCODE相等时，两值不一定相等所以这个算法在某些特定情况下会有错误，比如
"bc"和"ad"比较，值就为true,显然是不合要求的

Answer 7

不严谨，你用你的算法比较"bc"和"ad"，结果是错的

Answer 8

你说的哈希码相同时，不一定相等，是由这种情况。但你说ad和bc相等，难道你认为hashcode是连着顺序排放的吗？还是别的意思？

Answer 9

参考一下这个帖子。
http://bbs.csdn.net/topics/390164362

Answer 10

#include<stdio.h>
#include<string.h>
#include<stdlib.h> 
 
const int length = 128;int com(char * first, char * second){
int first_array[128];
int second_array[128]; 
char tmp;
int size1, size2;
size1 = strlen(first);
size2 = strlen(second);
 
if(size1 != size2){
return 0; 
}
for(int i=0; i<128; i++){
first_array[i] = 0;
second_array[i] = 0; 
} 
while((tmp = *first) != '\0'){
if(tmp>='A' && tmp<='Z'){
first_array[tmp+32]++; 
}
else{ 
first_array[tmp]++;
}
first++; 
}
 
  while((tmp = *second) != '\0'){
if(tmp>='A' && tmp<='Z'){
second_array[tmp+32]++; 
}
else{ 
second_array[tmp]++;
}
second++; 
}

for(int i=0; i<128; i++){
if(first_array[i] != second_array[i]){
return 0; 
}
}
return 1; 
}
int main(){
char * first_str = "ABC";
char * second_str = "bacd";
if(com(first_str, second_str)){
printf("equal"); 
}
else{
printf("not equal"); 
}
return 0; 
} 代码写的好烂，先做其他事儿去了，以后再改下

Answer 11

参考HashSet的哈希算法。Java code123456789101112     public static int getHashCode(String str){     int h=0;     for(Character c:str.toUpperCase().toCharArray()){         h+=c.hashCode();     }     return h;     }     public static void main(String[]args)     {     System.out.println(getHashCode("abc")==getHashCode("aca"));     } 
+1

Answer 12

能不能就是先把第一个转换成char然后去判断第二个里面有没有，没有就返回不一样，有的话就把当前相同的那个删除，最后如果第二个长度为0第一个也全部判断完了，就相同，如果第一个没有完就不相同。代码就不写了

Answer 13

1 箱排序，申请长度26的空间对应26个字母，初始化为0，遍历第一个串分别在对应位置自增1，遍历第二个串对应位置自减1.遍历的时候不区分大小写，最后循环一遍数组看是否全0判断串是否相等2 二叉查找树，用第一个串建立一个二叉查找树，第二个串不区分大小写删除二叉查找树的节点，最后删空的话就是相等，其他所有情况都是不等，这个其实就是对应的上面的用Set实现的算法，Set内部还平衡过。效率更好。
这个问题论坛里面好多好多好多好多。

Answer 14

我来总结一下：
方法1：比较str1和str2的长度，不等，则str1与str2不等。
若相等，先将两个字符都转化为大写或小写，然后对两个字符进行排序，再用equals比较。
方法2：先创建一个26大小的字符数组，依次存入字符0，然后将str1中字符依次遍历，在相应位置上+1；遍历str2，在相应位置上-1，看数组最后是否各位都为0.
方法3：将两字符串转化为大写或小写，设字符串长度为length，从0到length-1，对于str1中的字符，看str2中是否存在，存在则删除，继续遍历，直到str1中字符在str2中找不到对应的字符，则不等，或最终遍历完str1，则相等。不知道总结的是否全面，欢迎继续补充~
多谢大家

Answer 15

hashCode还是比较靠谱的，效率高。简单来说，可以这么理解：
1、把a,b,c,d……不分大小写，分别对应1,2,3,4……26，把字符串转化成int[]；
2、然后循环取给每个元素一个算法，得出一个值 (相当于求hash值)；
3、最后循环叠加这个值，得出最后的总数。  【通过这个总数就可以比较是否相等了】下面简单模拟一下这个算法，和11楼的hash算法是一个意思，只是分开来写，写得简单明了一些，并且尽量避免使用java的函数：
    // 字符转换成数字，相当于hashCode
    public static int[] getIntArray(String str) {   
        int[] arrRet = new int[str.length()];
        int i = 0;
        for (char ch : str.toUpperCase().toCharArray()) {
            arrRet[i++] = ch - 65;    // 这本身没有必要-65，只不过想变成1234…更好理解
        }
        return arrRet;
    }
    // 求和，原来也可以在循环转化成数字的时候做的，分开只是为了更容易理解。
    public static int sum(int[] arr) {   
        int sum = 0;
        for (int i : arr) {
            sum += i * i * i + 100;  // 随便搞的一个算法，相等于求hashCode
        }
        return sum;
    }
    public static void main(String[] args) {
        String s1 = "abc";
        String s2 = "bca";
        int sum1 = sum(getIntArray(s1));
        int sum2 = sum(getIntArray(s2));
        System.out.println(sum1 == sum2 ? "相等" : "不等");
    }

Answer 16

public class Test { public static void main(String[] args) {
String str1 = "abcabc";
String str2 = "abcaba";
System.out.println(check(str1, str2)); } public static boolean check(String str1, String str2) {
if (str1.length() != str2.length()) {
return false;
}
int[] arys = new int[26];
String str = str1 + str2;
for (int i = 0; i < str.length(); i++) {
arys[str.charAt(i) - 'a'] = arys[str.charAt(i) - 'a'] + 1;
}
for (int i = 0; i < arys.length; i++) {
if (arys[i] % 2 != 0) {
return false;
}
}
return true;
}
}

Answer 17

补充一下我在24楼写的  忘了大小问题了   加上toLowerCase()

Answer 18

还有，你这个算法考虑的不周全，比如说“abbaccdd”和“abbaaabb”比较，结果也为true。你只保证了两个数组中每个字符的个数和为偶数，但这个地方有漏洞，应该先遍历第一个字符串，在相应位置加1，再遍历第二个字符串减1.

Answer 19

用两个 26 的数组M和N，检索一遍字符串，如果遇到‘a’和‘A’就在M[0] 加1，遇到‘b'和‘B’就在M[1]加1。如此类推。
最后比较两个数组是否相等。

Answer 20

算法不严谨，只采用HASHCODE求和的方式是不能准确判断的
你用你的算法试试这个数据，你的算法得出的结果是相等
"aaaaaaaaaaa" 和 "k"

Answer 21

对对，没想这么多，知道会有冲突，没想到这么容易冲突，
还故意调一下Character的hashCode方法，原来也是直接取ascii值

Answer 22

public static boolean isEqual( final String xstr1, final String xstr2 ) { StringBuffer str1 = new StringBuffer( xstr1.toLowerCase() );
StringBuffer str2 = new StringBuffer( xstr2.toLowerCase() );
boolean result = true;
Character c = null; if( str1.length() == str2.length() ) {
int i = str1.length();
for( ; i>=1 ; i=str1.length() ) {
c = str1.charAt( i - 1 );
try {
str1 = str1.deleteCharAt( str1.indexOf( c.toString() ) );
str2 = str2.deleteCharAt( str2.indexOf( c.toString() ) );
}
catch(Exception e) {
result = false;
break;
}
}
}
else result = false;

return result;
}

Answer 23

我给每个字母使用素数编一个号，不区分大小写，比如：
 a-3,b-5,c-7,d-11.........
然后:
"abc" → ['a','b','c'] → [3,5,7] →3*5*7 = 105
"CaB" → ['C','a','B'] → [7,3,5] 
然后：
tmp
[7,3,5].each(fn(i){
 tmp = 105/i
});
tmp == 0 ?"相等":"不相等"

Answer 24

取每个字符串的各个字符，转化为INT求和。比较总和是否相等。

Answer 25

两string转小再转char，然后异或。结果为0就相等

Answer 26

26个字母转成ascii码 其中a=a+0*26 b=b+1*26 字母（X）= x + （当前所在位）*26； 
那么一个字符串的字母的和 和另外一个字符串字母和 比较是否相等 相等一样不相等不一样 

Answer 27

第一种所说的箱排序比较高效，算法复杂度是O(n)，最好情况为O(1)，最坏情况为O(n)。下面使用JavaScript展示一下箱排序的实现，为了支持UTF-8中所有的字符，实现稍微有点变形：
function assertStrEqual(str1, str2) {
    var charMap = {}, 
        c,
        i,
        len1 = str1.length,
        len2 = str2.length;    if (len1 != len2) {
        return false;
    }    for (i = len1; i--;) {
        c = str1.charAt(i).toLowerCase();
        charMap[c] = (charMap[c] || 0) + 1;
    }    for (i = len2; i--;) {
        c = str2.charAt(i).toLowerCase();
        if (charMap[c]) {
            charMap[c]--;
        } else {
            return false;
        }
    }    for (var key in charMap) {
        if (charMap.hasOwnProperty(key) && charMap[key] != 0) {
            return false;
        }
    }    return true;
}

Answer 28

public static void main(String[] args) {
// TODO Auto-generated method stub
aaa a = new aaa();
List list1 = a.getList("asdf");
List list2 = a.getList("fdsa");
String n1 ="";
int n2 = 0;
int n3 = 0;
for (int i = 0; i < list1.size(); i++) {
n1 = list1.get(i).toString();
for (int j = 0; j < list1.size(); j++) {
if(n1.equals(list1.get(j))){
n2++;
}
}
for (int j = 0; j < list2.size(); j++) {
if(n1.equals(list2.get(j))){
n3++;
}
}
if(n2 != n3){
System.out.println("两个字符串不相等！");
}
}
System.out.println("两个字符串相等！");
} // 转化为list
public List getList(String str) {
List list = new ArrayList();
for (int i = 0; i < str.length(); i++) {
if (i == 0) {
list.add(str.substring(0, 1));
} else {
list.add(str.substring(i, i + 1));
}
}
return list;
}

Answer 29

import java.util.ArrayList;
import java.util.List;public class Tests {
public static void main(String[] args) {
Tests test = new Tests();
List list1 = test.getList("asdf");
List list2 = test.getList("fdsa");
String n1 = "";
int n2 = 0;
int n3 = 0;
for (int i = 0; i < list1.size(); i++) {
n1 = list1.get(i).toString();
for (int j = 0; j < list1.size(); j++) {
if (n1.equals(list1.get(j))) {
n2++;
}
}
for (int j = 0; j < list2.size(); j++) {
if (n1.equals(list2.get(j))) {
n3++;
}
}
if (n2 != n3) {
System.out.println("两个字符串不相等！");
}
}
System.out.println("两个字符串相等！");
} // 转化为list
public List getList(String str) {
List list = new ArrayList();
for (int i = 0; i < str.length(); i++) {
if (i == 0) {
list.add(str.substring(0, 1));
} else {
list.add(str.substring(i, i + 1));
}
}
return list;
}
}第一次发这种代码格式的。。郁闷 上面的发完就感觉不对

Answer 30

我来贴一个：package exec.basic;import java.util.Scanner;public class StrEqual {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
String str=sc.nextLine();
String str2=sc.nextLine();
str=str.toLowerCase();
str2=str2.toLowerCase();
if(str.length()!=str2.length()){
System.out.println("两字符串不等。");
System.exit(0);
}
int arr[]=new int[26];
for(int i=0;i<arr.length;i++)
arr[i]=0;
for(int i=0;i<str.length();i++){
char ch=str.charAt(i);
int j=ch-97;
arr[j]+=1;
}
for(int i=0;i<str.length();i++){
char ch=str2.charAt(i);
int j=ch-97;
arr[j]-=1;
}
int count=0;
for(int i=0;i<arr.length;i++){
if(arr[i]==0)
count++;
}
if(count==26)
System.out.println("str和str2相等。");
else
System.out.println("str和str2不等。");
}
}