Two Sum

☆☆☆☆☆

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<Integer, Integer>();
    for (int i = 0; i < nums.length; ++i) {
        if (seen.containsKey(target - nums[i])) 
            return new int[]{seen.get(target - nums[i]) + 1, i+1};
        else 
            seen.put(nums[i], i);
    }
    return new int[]{0,0};
}

Valid Anagram

★★☆☆☆

Given two strings s and t, write a function to determine if t is an anagram of s.

For example, s = "anagram", t = "nagaram", return true. s = "rat", t = "car", return false.

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] counter = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            counter[s.charAt(i) - 'a']++;
            counter[t.charAt(i) - 'a']--;
        }
        for (int i = 0; i < 26; ++i) {
            if (counter[i] != 0) return false;
        }
        return true;
    }
}

Group Anagrams

★★☆☆☆

Given an array of strings, group anagrams together. For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: For the return value, each inner list's elements must follow the lexicographic order. All inputs will be in lower-case.

Note

• Sort first in strs will assure answer also has right order
• Sort the components in anagrams to assure unique hashmap key!

public List<List<String>> groupAnagrams(String[] strs) {
    if (strs == null || strs.length == 0) return new ArrayList<List<String>> ();
    Arrays.sort(strs);
    Map<String, List<String>> hmap = new HashMap<String, List<String>>();
    for (String s : strs) {
        char[] key = s.toCharArray();
        Arrays.sort(key);
        String keyStr = String.valueOf(key);
        if (!hmap.containsKey(keyStr)) hmap.put(keyStr, new ArrayList<String>());
        hmap.get(keyStr).add(s);
    }
    return new ArrayList<List<String>>(hmap.values());
}