Algorithm - LeetCode Problems 6

Problem 49. Group Anagrams

• Given an array of strings strs, group the anagrams together. You can return the answer in any order.

• An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Examples

• Example 1:

  • Input: strs = ["eat","tea","tan","ate","nat","bat"]
  • Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

• Example 2:

  • Input: strs = [""]
  • Output: [[""]]

• Example 3:

  • Input: strs = ["a"]
  • Output: [["a"]]

Constraints

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

Solution

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    let anagramObj = {};
    
    for (const word of strs) {
        const sortedWord = word.split('').sort().join('');
        if (anagramObj[sortedWord]) {
            anagramObj[sortedWord].push(word);
        } else {
            anagramObj[sortedWord] = [word];
        }
    }

    return Object.values(anagramObj);
};

Problem 2390. Removing Stars From a String

• You are given a string s, which contains stars *.

• In one operation, you can:

• Choose a star in s.

  • Remove the closest non-star character to its left, as well as remove the star itself.
  • Return the string after all stars have been removed.

• Note:

  • The input will be generated such that the operation is always possible.
  • It can be shown that the resulting string will always be unique.

Examples

• Example 1:

  • Input: s = "leet**cod*e"
  • Output: "lecoe"
  • Explanation:
    • Performing the removals from left to right:
    • The closest character to the 1st star is 't' in "leet**cod*e". s becomes "lee*cod*e".
    • The closest character to the 2nd star is 'e' in "lee*cod*e". s becomes "lecod*e".
    • The closest character to the 3rd star is 'd' in "lecod*e". s becomes "lecoe".
    • There are no more stars, so we return "lecoe".

• Example 2:

  • Input: s = "erase*****"
  • Output: ""
  • Explanation:
    • The entire string is removed, so we return an empty string.

Constraints

• 1 <= s.length <= 10^5
• s consists of lowercase English letters and stars *.
• The operation above can be performed on s.

Solution

/**
 * @param {string} s
 * @return {string}
 */
var removeStars = function(s) {
    const stack = [];

    for (let i = 0; i < s.length; i++) {
        const str = s[i];
        if (str === '*') {
            stack.pop();
        } else {
            stack.push(str)
        }
    }

    return stack.join('');
};

Problem 463. Island Perimeter

• You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.

• Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

• The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

Examples

• Example 1:
  • Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
  • Output: 16
  • Explanation: The perimeter is the 16 yellow stripes in the image below.

• Example 2:
  • Input: grid = [[1]]
  • Output: 4

Constraints

• row == grid.length
• col == grid[i].length
• 1 <= row, col <= 100
• grid[i][j] is 0 or 1.
• There is exactly one island in grid.

Solution

/**
 * @param {number[][]} grid
 * @return {number}
 */
var islandPerimeter = function(grid) {
    const row = grid.length;
    const col = grid[0].length;
    let totalPerimeter = 0;

    const getPerimeter = function(rowIndex, colIndex) {
        const dx = [1, -1, 0, 0];
        const dy = [0, 0, 1, -1];
        let perimeter = 4;

        for (let i = 0; i < dx.length; i++) {
            const nextRow = rowIndex + dx[i];
            const nextCol = colIndex + dy[i];

            if (nextRow < 0 || nextRow >= row || nextCol < 0 || nextCol >= col) {
                continue;
            }

            if (grid[nextRow][nextCol]) {
                perimeter -= 1;
            }
        }

        return perimeter;
    }

    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if (!grid[i][j]) {
                continue;
            }
            totalPerimeter += getPerimeter(i, j);
        }
    }

    return totalPerimeter;
};