php Question posted in
Official manual can be found here.

PHP Solution to Leetcode "Group Anagrams" without Set Data Structure

For the problem Leetcode problem here, here’s my solution in PHP. Most examples found are Python and so much shorter using Sets.

The question itself has not target space or time complexity and my question is if there is a more efficient PHP solution.

class Solution {
/**
 * @param String[] $strs
 * @return String[][]
 */
function groupAnagrams($strs) {
    $result = [];
    $alreadyPlaced = [];
    $currentPalindromes = [];
    $hashed = [];

    foreach($strs as $key => $str) {
        // create assoc array mapping letter to index of str its from
        if ( array_key_exists($key, $alreadyPlaced) ) continue;

        // mark this as placed
        $alreadyPlaced[$key] = true;

        // initiatilize new array and place into new array
        $currentPalindromes = array();
        array_push($currentPalindromes, $str);

        // to be able to determine palindromes, hash each letter in the newly found string
        $hashed = array();
        foreach (str_split($str) as $c) {
            $hashed[$c] = true;
        }

        //loop thru all strings skipping those of not same length or already accounted for
        foreach($strs as $checkKey => $checkVal) {
            $breakout = false;
            if (mb_strlen($checkVal) != mb_strlen($str)) continue;
            if (array_key_exists($checkKey, $alreadyPlaced)) continue;
            foreach (str_split($checkVal) as $c) {
                
                if (!$hashed[$c]) {
                    $breakout = true;
                    continue;
                }
            }
            if ($breakout) continue;
            // if it got here, its a palindrome
            array_push($currentPalindromes, $checkVal);
            $alreadyPlaced[$checkKey] = true;
        }
        //add new palindrome array into $result array
        array_push($result, $currentPalindromes);
    }
    return $result;        
}
Tags:

2

Answers


  1. 0

    You have way too much code here. You start well, but overcomplicate the process of grouping the anagrams. Here’s my solution:

    <?php

/**
 * Solution.php
 *
 */
class Solution {
  public function groupAnagrams(array $strs) {
      $output = [];
      foreach($strs as $anagram) {
          $strArray = str_split($anagram);
          sort($strArray);
        $output[join($strArray)][] = $anagram;
      }
        return array_values($output);
  }
}

    This simplifies the process by sorting the characters in each source string. Each anagram of a given word will generate the same sorted list, which makes it easy to compare anagrams.

    Use that sorted anagram as an index into an associative array, and add the original word to an array at that index. If the anagram hasn’t been seen a new entry is created. If it has, the word is added to the output array.

    Finally, return only the values from the associative array to meet the requirements of the challenge.

    The solution is accepted for both run time and memory.

    Login or Signup to reply.
  2. 0
    • Your algorithm running time is O(N x N x M).
    • We can optimize it further, and avoid using sort() since the sort() itself is O(N Log N), which makes the total running time O(N x N x Log N):
    class Solution
{
    function groupAnagrams($strs)
    {
        $res = [];
        foreach ($strs as $word) {
            $hash = $this->genHash($word);
            $res[$hash][] = $word;
        }
        return $res;
    }

    function genHash($word)
    {
        $count = array_fill(0, 26, 0);
        $alpha = ord('a');
        for ($i = 0; $i < strlen($word); $i++) {
            $count[ord($word[$i]) - $alpha]++;
        }
        return implode(',', $count);
    }
}

function run()
{
    $solution = new Solution();
    print_r($solution->groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]));
}

run();

    Results:

    Array
(
    [1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0] => Array
        (
            [0] => eat
            [1] => tea
            [2] => ate
        )

    [1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0] => Array
        (
            [0] => tan
            [1] => nat
        )

    [1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0] => Array
        (
            [0] => bat
        )

)
    • Time Complexity: O(N x M)
    • Space Complexity: O(N x M)
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search