Time Limit Exceeded ~ How to improve? (JAVA)


  • 0
    H

    I don't know what part taking so long, any idea? Thank you!

    public class Solution {
      public List<List<String>> groupAnagrams(String[] strs) {
            
        List<List<String>> result = new ArrayList<>();
        boolean[] toResult = new boolean[strs.length];
        for (int i = 0; i < strs.length; i++) {
          if (toResult[i]) {
            continue;
          }
          List<String> partialResult = new ArrayList<>();
          partialResult.add(strs[i]);
          toResult[i] = true;
          for (int j = i + 1; j < strs.length; j++) {
            if (isAnagram(strs[i], strs[j])) {
              partialResult.add(strs[j]);
              toResult[j] = true;
            }
          }
          result.add(partialResult);
        }
        return result;
      }
      private static boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
          return false;
        }
        HashMap<Character, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
          Character c = s.charAt(i);
          if (hashMap.containsKey(c)) {
            hashMap.put(c, hashMap.get(c) + 1);
          } else {
            hashMap.put(c, 1);
          }
          Character c2 = t.charAt(i);
          if (hashMap.containsKey(c2)) {
            hashMap.put(c2, hashMap.get(c2) - 1);
          } else {
            hashMap.put(c2, -1);
          }
        }
        for (int freqDiff : hashMap.values()) {
          if (freqDiff != 0) {
            return false;
          }
        }
        return true;
      }
    }
    

  • 0

    @hsiao-ying

    • anagrams should be equal after being sorted
    • hash map can be used to collect different words while the key is the sorted word

Log in to reply
 

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