算法题: 打印含有相同字符的数组

Write a function that takes as input list of words and prints out groups of words with exactly the same letters, one group per line.

For example,

Given the list:
hat, top, potter, pot, pier, ripe

It would print:
hat
top, pot
potter,
pier, ripe

Since ‘pier’ and ‘ripe’ each have one p, i, e, and r they belong on the same line. Since no other word has the same 6 letters as ‘potter’ it belongs on a line by itself.

Note: The order of the lines does not matter. As long as all words that belong on the same line are grouped together the function is correct.

Please use the following function signature:

void PrintGroupsWithSameLetters(string[] words)

 

http://www.iteye.com/topic/1120051

 

评论

2 楼 greatwqs 2012-02-03  

static void PrintGroupsWithSameLetters( String[] words )
    {
        Map map = new LinkedHashMap();
        for( String word : words )
        {
            char[] charArray = word.toCharArray();
            Arrays.sort( charArray );
            String key = String.valueOf( charArray );
            if( map.get( key ) != null )
            {
                map.put( key, map.get( key ) + "," + word );
            }
            else
            {
                map.put( key, word );
            }
        }
        Iterator iterator = map.entrySet().iterator();
        while( iterator.hasNext() )
        {
            System.out.println( ( ( Map.Entry ) iterator.next() ).getValue() );
        }
    }

1 楼 greatwqs 2012-02-03  

利用素数乘积唯一性

import java.util.HashMap;
import java.util.Map;

public class PrintGroupsWithSameLetters {

	private static final int[] 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 };

	public static void main(String[] args) {
		String[] sample = { "hat", "top", "potter", "pot", "pier", "ripe" };
		PrintGroupsWithSameLetters.PrintGroupsWithSameLetters(sample);
	}

	public static void PrintGroupsWithSameLetters(String[] words) {
		Map map = new HashMap();
		for (int index = 0; index < words.length; index++) {
			PrintGroupsWithSameLetters.insertOrUpdate(map, words[index],
					getValue(words[index]));
		}
		System.out.println(map);
	}

	public static void insertOrUpdate(Map lib, String word, int value) {
		if (!lib.containsKey(value)) {
			lib.put(value, word);
		} else {
			lib.put(value, lib.get(value) + "," + word);
		}
	}

	public static int getValue(String word) {
		if (word == null || "".equals(word.trim())) {
			return -1;
		}
		word = word.toLowerCase();
		int value = 1;
		char letter[] = word.toCharArray();
		for (int index = 0; index < letter.length; index++) {
			int temp = letter[index] - 'a';
			if (temp < 0 || temp > 25) {
				return -1;
			}
			value *= prime[temp];
		}
		return value;
	}
}