Goldman Sachs新鲜电面

roommate

$ y; i: \% I8 ^! u
You have String array like{'cat','good','tac','act''....} like some 1000 words.
# o. M8 e( m$ F+ S: QSo if i give input tac ,output should be cat and act..
% c8 N6 K* E3 f! Q4 l. EHow can we implement with less complexity

Cecil_Cai

private static void anagram(String[] str1,String searchString) {
		// TODO Auto-generated method stub
% r! a0 a8 F+ J		for(String s:str1)
6 c( L9 W6 O( D( [" Q# L		{
5 w2 r. w4 s9 n" @& D			if(sort(searchString).equals(sort(s)))
			{
				System.out.println(s);
			}
7 j2 b9 q/ Z1 _+ ]$ g		}
% N! j$ a6 ?7 c+ m' ~. G	}

弱弱求offer

1. Create a HashMap<Integer, List<String>> that will hold every String from your array of strings using as Key the sum of each char Integer value. # l* Q' H$ D; v' q3 _
' p' P. a6 F/ m: V) v
2. Iterate over your list and insert each string using as key a transformation function that will calculate the sum of every char on that string, thus strings with same chars will have exact same sum. Append the Strings with same sum into the List of Strings for that particular sum. ' `# L! b8 K- m! u ~
) {/ P, G$ T6 G4 l: b/ D. I# {
3. for your String as input, just get it's sum value using the same transformation function, once you have the sum use it as key to print the resulting List<String> of the HashMap, that will print all Strings with same chars. * f9 J( X& `4 J/ t2 A/ |
, M8 ]/ ~% ]+ x& i
- O(n * n) to build list, O(1) to print String list & q) K, r& ~& O3 H' _- _
- O(n) space