249. Group Shifted Strings-白红宇

249. Group Shifted Strings

阅读量：4627 次

发布时间：2019-06-09

本文共 5351 字，大约阅读时间需要 17 分钟。

题目：

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"],

Return:

[  ["abc","bcd","xyz"],  ["az","ba"],  ["acef"],  ["a","z"]]

Note: For the return value, each inner list's elements must follow the lexicographic order.

链接：

题解：

一道简单题，我又写得巨长...水平太有限了，唉。主要是数据结构选了一个Map<Integer, Map<String, List<String>>>，先以String长度为key，再以单词为key，List<String>为value。其实可以不用这么麻烦，就用Map<String，List<String>>就可以了。遍历keySet()的时候，只要长度不一样，continue就行了。时间复杂度还是一样的。假设单词长度有限的情况下，还是O(n²)。二刷再简化..........这句话说了几百遍。二刷再简化吧！

Time Complexity - O(n²)， Space Complexity - O(n)。

public class Solution {    public List
     
      
       > groupStrings(String[] strings) {        List
       
        
         > res = new ArrayList<>();        if(strings == null || strings.length == 0)            return res;        Arrays.sort(strings);                    Map
         
          >> map = new HashMap<>();                for(int i = 0; i < strings.length; i++) {            String s = strings[i];            int len = s.length();            if(!map.containsKey(len)) {                Map
          
           > tmpMap = new HashMap<>(); tmpMap.put(s, new ArrayList<>(Arrays.asList(s))); map.put(len, tmpMap); } else { Map
           
            > tmpMap = map.get(len); boolean hasSequence = false; outerloop: for(String t : tmpMap.keySet()) { for(int k = 1; k < len; k++) { int curDistance = (int)(s.charAt(k) - t.charAt(k)); int lastDistance = (int)(s.charAt(k - 1) - t.charAt(k - 1)); curDistance = curDistance >= 0 ? curDistance : curDistance + 26; lastDistance = lastDistance >= 0 ? lastDistance : lastDistance + 26; if(curDistance != lastDistance) continue outerloop; } tmpMap.get(t).add(s); hasSequence = true; break; } if(!hasSequence) { tmpMap.put(s, new ArrayList<>(Arrays.asList(s))); } } } for(int i : map.keySet()) { Map
            
             > tmpMap = map.get(i); for(String s : tmpMap.keySet()) { res.add(map.get(i).get(s)); } } return res; }}

二刷：

二刷就好一些。之前写得比较乱也不容易懂，下面来分析二刷的想法。

主要是利用和求anagram一样的方法，利用HashMap来保存能group到一起的单词

对于能group到一起的每个单词来说，他们都会有一个base case，每个单词都是从这个base case shift出去的，比如 abc, bcd, cde一类的，我们可以把abc认定为base case，那么所有base case为abc的单词，我们就可以group到一起

了解了原理，接下来我们就可以操作实现了，首先我们有一个HashMap<String，List<String>>，这里的key是base case String，比如abc, ab, a一类的, 而value List<String>就是可以被放入结果集中的List

我们遍历给定的数组Strings，对于每一个单词s，
1. 我们求出它的base case string
  1. 这里另外写了一个球base case string的方法getBaseStr
  2. 我们假定所有的base case string均以'a'为第一个字母
  3. 求出第一个字母被shift的长度lenShifted = s.charAt(0) - 'a'，并且建立一个StringBuilder用来保存结果
  4. 接下来对于string s中的每一个字母c，我们计算他在被移动lenShifted个长度之前的字母是什么
    1. 我们可以用c - 'a'求出c到'a'的距离，再减去这个lenShifted，就得到了当前这个字母究竟被shift了多少个单位curShifted
    2. 之后处理一下特殊情况，当这个curShifted < 0的时候，我们要加上26，把它重新映射到26个小写字母里
    3. 最后求出c = char('a' + curShifted)，这时更新后的c就是 shift之前的base char
    4. 我们把这个base char存入StringBuilder里，接着计算下一个字符。 (这里也可以使用stefan pochmann的写法大大简化代码）
    5. 最后返回sb.toString()就是我们要求的base case string
2. 得到base case string把单词按照base case string存入到hashmap里

遍历完毕以后，我们还要对HashMap中的每个group进行排序

最后利用hashMap的结果集合values生成最终结果，即 res = new ArrayList<List<String>>(map.values());

Java:

Time Complexity - O(nlogn)， Space Complexity - O(n)。

public class Solution {    public List
     
      
       > groupStrings(String[] strings) {        List
       
        
         > res = new ArrayList<>();        if (strings == null || strings.length == 0) {            return res;        }        Map
         
          > map = new HashMap<>();        for (String s : strings) {            String base = getBaseStr(s);            if (!map.containsKey(base)) {                map.put(base, new ArrayList<>());            }            map.get(base).add(s);        }        for (String s : map.keySet()) {            Collections.sort(map.get(s));        }        res = new ArrayList
          
           
            >(map.values()); return res; } private String getBaseStr(String s) { if (s == null || s.length() == 0) { return s; } StringBuilder sb = new StringBuilder(); int lenShifted = s.charAt(0) - 'a'; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); int curShifted = c - 'a' - lenShifted; if (curShifted < 0) { curShifted += 26; } c = (char)('a' + curShifted); sb.append(c); } return sb.toString(); }}

Reference:

https://leetcode.com/discuss/50358/my-concise-java-solution

https://leetcode.com/discuss/69783/concise-10-lines-java-solution-with-explanation

https://leetcode.com/discuss/67240/around-13-lines-code-in-java

https://leetcode.com/discuss/64979/simple-solution-in-java-with-detailed-explaination

https://leetcode.com/discuss/64751/cannot-pass-tests-seems-nothing-wrong-for-the-custom-testcase

https://leetcode.com/discuss/58003/java-solution-with-separate-shiftstr-function

https://leetcode.com/discuss/53166/4ms-c-solution

https://leetcode.com/discuss/52627/python-easy-to-understand-solution-with-comments

https://leetcode.com/discuss/50582/4ms-c-solution

https://leetcode.com/discuss/50557/4ms-easy-c-solution-with-explanations

https://leetcode.com/discuss/50416/1-4-lines-in-java

https://leetcode.com/discuss/50163/1-4-lines-ruby-and-python

转载于:https://www.cnblogs.com/yrbbest/p/5009004.html

你可能感兴趣的文章