LeetCode 249. Group Shifted Strings （群组移位字符串）$

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/

巴特西

LeetCode 249. Group Shifted Strings （群组移位字符串）$

最新文章

热门文章