给大家出道题，算法的

怎么说呢，我怀疑这样的移位是不是OK    

bcde对应的移位   是这样的
0001,0002,0003,0004
移位后是这样，
0010
0100
0110
1000然后再与对吧
我不管结果，总之对于2进制来说是1110对不
那么我再来一组
0010
0100
1110
1000
接着看呢，结果还是1110，我有N种变化都对应1110而且   N种不同的字符，所以，我个人认为不可靠！

个人觉得这个算法有点问题，比如会认为 bottle 和botle是同一组：

Agree.

I think this is the most easiest and efficient algorithm until now. This algorithm takes O(N) time and O(N) space.

By the way, Java Arrays.sort() takes O(logN) space and O(NlogN) time.

I put the Java code here.

public static boolean process(String[] array) {
		if(array == null) {
			return false;
		}
		
		if(array.length == 0) {
			return false;
		}
		
		if (array.length == 1) {
			System.out.println("Line: " + array[0]);
			return true;
		}
		
		// Generate fingerprint for each string 
		HashMap hm = new HashMap();
		for(String str: array) {
			String fp_key = getFingerprint(str);
			
			if (hm.containsKey(fp_key)) {
				List list = (List) hm.get(fp_key);
				list.add(str);
			} else {
				List list = new ArrayList();
				list.add(str);
				hm.put(fp_key, list);
			}
		}
		
		// Print a set of strings which have the same fingerprint
		Set keys = hm.keySet();
		Iterator it = keys.iterator();
		while(it.hasNext()) {
			String fp_key = (String) it.next();
			List list = (List) hm.get(fp_key);
			
			printWords(list);
		}
		return true;
	}
	
        // the way to generate fingerprint for a string really depends
	public static String getFingerprint(String str) {
		/*
		StringBuffer fp = new StringBuffer();
		char[] array = str.toCharArray();
		Arrays.sort(array);
		
		int count = 1;
		for(int i = 0; i < array.length - 1; i ++) {
			if (array[i] == array[i + 1]) {
				count ++;
			} else {
				fp.append(array[i]);
				fp.append(count);
				count = 1;
			}
		}
		
		fp.append(array[array.length - 1]);
		fp.append(count);
		
		return fp.toString();
		*/
		
		
		char[] array = str.toCharArray();
		Arrays.sort(array);
		String fp = new String(array);
		return fp;
	}
	
	public static void printWords(List list) {
		System.out.print("This line: ");
		
		Iterator it = list.iterator();
		while(it.hasNext()) {
			System.out.print(it.next() + " ");
		}
		
		System.out.println();
	}

Please let me know if we can get better big O for both time and space. Thank you guys.

I think this is pretty new idea for me. Could you please explain the idea in plain text ? Thanks

给个clojure的代码吧：

user> (vals (group-by #(set %) ["hat","top","potter","pot","pier","ripe"]))
(["hat"] ["top" "pot"] ["potter"] ["pier" "ripe"])

1.get the value of each word. A word's value is the product of each letter in it.like the value of "hat" is prime['h'-'a']*prime['a'-'a']*prime['t'-'a']
2.if Map already contains the key(it's the product above),then update the corresponding value.Otherwise just put it into Map

高人

这个问题细分为两个问题：
一、两个字符串是否相同？
算法： 第一步，判断两个字符串长度是否相同？
        第二步，计算出每个字符串中所有字符的ascii码值之和，判断两个字符串对应的和是否相同？（大部分情况到这里就能得到结果）
        第三步，计算两个字符串包含的字符和对应字符出现次数是否相同？(少部分会到达第三步)
二、怎么为格式化输出准备结果？
顺序遍历字符串数组，与结果Map<String,List<String>>中的key依次比较，如果相同，则在当前key对应的value中添加当前字符串，map中都没有该字符串时，往map中添加一个。

不知道这样描述清楚没~，这个算法，二中的处理可能不够高效。字符串数量多之后就慢了。

呵呵，我想多了，脑子每天都大数据计算。 把问题复杂化了 

jdk用的是归并排序，这里有些不合适，效率不高
改用先统计每个字母的数量再组装字符串，效率提高一倍

public static String sort(String s){
//26个字母
short[] t =new short[26];
char c[]=s.toCharArray();
for(short i=0;i<c.length;t[c[i++]-'a']++) ;
for(short i=0,j=0;i<26&&j<c.length;i++){
for(short k=1;k<=t[i];k++){
c[j++]=(char)(i+'a');
}
}
return new String(c);
}
[\code]
下面有就有个问题了，对于程序来说，字符串是什么，还不是char[]，这里我们再思考下，反正都是要比较的，我直接把上面的那个short []t丢出来比较是不是更快

public class Comparable {
public short[] t;
public Comparable(String s){
t=PP.sort2(s);
}
@Override
public boolean equals(Object paramObject) {
if(paramObject==null) return false;
if(paramObject instanceof Comparable){
Comparable cast = (Comparable)paramObject;
if(cast.t.length!=this.t.length) return false;
for(int i=0;i<cast.t.length;i++){
if(cast.t[i]!=this.t[i]) return false;
}
return true;
}
return false;
}
@Override
public int hashCode() {
int r=0;
for(int i=0;i<t.length;i++){
r+=r*31+t[i];
}
return r;
}

}
[\code]

完整测试代码

public class PP {
public static void main(String[] args) {
String s="cccabcfdjfdisojfiosfuqjofjidosjfasofusafus";
double time = System.currentTimeMillis();
for(int i=0;i++<1000000;Arrays.sort(s.toCharArray()));
double time2 = System.currentTimeMillis();
System.out.println((time2-time));
for(int i=0;i++<1000000;sort(s));
double time3 = System.currentTimeMillis();
System.out.println(time3-time2);
for(int i=0;i++<1000000;sort2(s));
double time4 = System.currentTimeMillis();
System.out.println(time4-time3);
String str=new String(s);
double time5 = System.currentTimeMillis();
for(int i=0;i++<1000000;s.equals(str));
double time6 =System.currentTimeMillis();
System.out.println(time6-time5);
Comparable c1= new Comparable(s);
Comparable c2 =new Comparable(s);
double time7 = System.currentTimeMillis();
for(int i=0;i++<1000000;c1.equals(c2));
double time8= System.currentTimeMillis();
System.out.println(time8-time7);
}

public static String sort(String s){
//26个字母
short[] t =new short[26];
char c[]=s.toCharArray();
for(short i=0;i<c.length;t[c[i++]-'a']++) ;
for(short i=0,j=0;i<26&&j<c.length;i++){
for(short k=1;k<=t[i];k++){
c[j++]=(char)(i+'a');
}
}
return new String(c);
}
public static short[] sort2(String s){
//26个字母
short[] t =new short[26];
char c[]=s.toCharArray();
for(short i=0;i<c.length;t[c[i++]-'a']++) ;
return t;
}
}
class Comparable {
public short[] t;
public Comparable(String s){
t=PP.sort2(s);
}
@Override
public boolean equals(Object paramObject) {
if(paramObject==null) return false;
if(paramObject instanceof Comparable){
Comparable cast = (Comparable)paramObject;
if(cast.t.length!=this.t.length) return false;
for(int i=0;i<cast.t.length;i++){
if(cast.t[i]!=this.t[i]) return false;
}
return true;
}
return false;
}
@Override
public int hashCode() {
int r=0;
for(int i=0;i<t.length;i++){
r+=r*31+t[i];
}
return r;
}
}
[\code]

结果
1827.0
968.0
410.0
225.0
142.0
(1827+225)/(410+142)≈3.7
差不多比自己写的耗时多3.7倍

不知道大家能不能理解，利用质数方法是不错，但是字符串长度过大的话，BigInteger的性能太差，它内部其实还是数组，依次遍历相乘再进位的算法，很慢