groupAnagrams.js

groupAnagrams.js

// Given an array of strings, group anagrams together.
/**
 * @param {string[]} strs
 * @return {string[][]}
 * @description Given an array of strs, group anagrams together.
 * @note inputs will be in lowercase.
         The order of your output does not matter.
 */


export function groupAnagrams(strs) {
  if (strs.length === 0) return [];
  let results = [[strs[0]]];
  strs = strs.slice(1);

  for (let i = 0; i < strs.length; i++) {
    const anagram = strs[i];
    results = addToGroup(results, anagram);
  }
  return results;
}

/**
 * [arrof Array] str → [arrof Array]
 * iterate over each goup to match anagram, if no match add new group with
 * anagram
 */

export function addToGroup(groups, anagram) {
  const results = [...groups];
  let noMatch = true;
  for (let j = 0; j < results.length; j++) {
    const targetGroup = results[j];
    const firstMemberGroup = targetGroup[0];
    const iHaveMatch = isAnagram(firstMemberGroup, anagram);
    if (iHaveMatch) {
      results[j].push(anagram);
      noMatch = false;
    }
  }
  // didn't found match, add to new group
  noMatch && results.push([anagram]);
  return results;
}

/**
 * String String → Boolean
 * produce true if item is anagram of target
 */
// my orginal idea
export function isAnagram(w1, w2) {
  if (w1.length !== w2.length) return false;

  Array.from(w1).forEach(ch => {
    w2 = removeAt(w2, w2.indexOf(ch));
  });

  return w2.length === 0;
}

export function removeAt(str, index) {
  return str.slice(0, index) + str.slice(index + 1);
}

// interesting approach
function isAnagram2(w1, w2) {
  if (w1.length !== w2.length) return false;
  Array.from(w1).forEach(c => (w2 = w2.replace(c, "")));
  return w2.length === 0;
}

// me after reading multiple leetcode answers
function groupAnagrams_(strs) {
  const map = new Map();
  for (let i = 0; i < strs.length; i++) {
    // prettier-ignore
    const anagram = Array.from(strs[i]).sort().join("");
    if (!map.get(anagram)) {
      map.set(anagram, [strs[i]]);
    } else {
      const group = map.get(anagram);
      group.push(strs[i]);
    }
  }
  return Array.from(map.values());
}