Two solutions, which way is better in general?


  • 0
    E

    We can sort the string first and then add into the list one after another, or alternatively, we can add the list first and then for every row inside the list, we sort it. If the strings are evenly distributed and assume there are N strings in the array, which are divided into k groups. Two treatments end up with the following complexity:

    • sort at the beginning: N * log(N)
    • sort after added into the list: N/k * log(N/k) * k = N * log(N/k)

    Theoretically, the second one should be better, right?

    BTW, here is the code for two treatments:

    1. sort at the beginning:

      public class Solution {
      public List<List<String>> groupStrings(String[] strings) {
      List<List<String>> list = new ArrayList<>();
      int L = strings.length;
      if(L<1) return list;
      
      HashMap<String, Integer> map = new HashMap<>();
      Arrays.sort(strings);
      for(String str : strings) {
          String strHash = convert(str);
          if(map.containsKey(strHash))
              list.get(map.get(strHash)).add(str);
          else {
              List<String> innerList = new ArrayList<>();
              innerList.add(str);
              list.add(innerList);
              map.put(strHash, list.size()-1);
          }
      }
      return list;
      }
      
      private String convert(String str) {
      String res = "a";
      int diff = str.charAt(0) - 'a';
      for(int i=1; i<str.length(); i++) 
          res += Character.toChars((str.charAt(i)-diff+26)%26)[0]; // add 26 and mod it so that az is the same as ba
      return res;
      }
      }
      
    2. sort after added into the list:

      public class Solution {
      public List<List<String>> groupStrings(String[] strings) {
      List<List<String>> list = new ArrayList<>();
      int L = strings.length;
      if(L<1) return list;
      HashMap<String, Integer> map = new HashMap<>();
      for(String str : strings) {
          String strHash = convert(str);
          if(map.containsKey(strHash))
              list.get(map.get(strHash)).add(str);
          else {
              List<String> innerList = new ArrayList<>();
              innerList.add(str);
              list.add(innerList);
              map.put(strHash, list.size()-1);
          }
      }
      List<List<String>> res = new ArrayList<>();
      for(List<String> l : list) {
          Collections.sort(l);
          res.add(l);
      }
      return res;
      }
      
      private String convert(String str) {
      String res = "a";
      int diff = str.charAt(0) - 'a';
      for(int i=1; i<str.length(); i++) 
          res += Character.toChars((str.charAt(i)-diff+26)%26)[0]; // add 26 and mod it so that az is the same as ba
      return res;
      }
      }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.