Given a string, we can "shift" each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep "shifting" which forms the sequence:
"abc" -> "bcd" -> ... -> "xyz"
Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.
For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
A solution is:
[
["abc","bcd","xyz"],
["az","ba"],
["acef"],
["a","z"]
]
题目标签：Hash Table
题目给了我们一个 strings array，让我们把不同移位距离的string 分开归类。
首先来看一下相同移位距离string 的特性：
相同的移位string，拥有相同的移位距离，比如abc, bcd, xyz 都是移位了1个距离。根据这个特性，我们可以把bcd 和 xyz 恢复到 abc。
利用HashMap，把最原始的 归位string 当作key，把可以恢复到 原始的 归位string 的 所有strings（List）当作value 存入map。
Java Solution:
Runtime beats 44.74%
完成日期：11/04/2017
关键词：HashMap
关键点：利用 char - 'a' 把所有相同移位距离的strings 转换成 同一个原始string 存入map
class Solution
{
public List<List<String>> groupStrings(String[] strings)
{
List<List<String>> res = new ArrayList<>(); HashMap<String, List<String>> map = new HashMap<>(); // store original string as key; (List) strings come from same original one as value
for(String str: strings)
{
int offset = str.charAt(0) - 'a';
String key = ""; for(int i=0; i<str.length(); i++)
{
char c = (char) (str.charAt(i) - offset);
if(c < 'a')
c += 26; key += c;
} if(!map.containsKey(key))
map.put(key, new ArrayList<String>()); map.get(key).add(str); } // add each key's value into res
for(String key: map.keySet())
{
res.add(map.get(key));
} return res;
}
}
参考资料：
https://discuss.leetcode.com/topic/20722/my-concise-java-solution
LeetCode 题目列表 - LeetCode Questions List
题目来源：https://leetcode.com/