Daniel P. Gleason

Category: LeetCode Solutions

  • Leetcode 1768 – Merge Strings Alternatively

    You are given two strings word1 and word2. Merge the strings by adding letters in alternating order, starting with word1. If a string is longer than the other, append the additional letters onto the end of the merged string.

    Return the merged string.

    Example 1:

    Input: word1 = "abc", word2 = "pqr"
Output: "apbqcr"
Explanation: The merged string will be merged as so:
word1:  a   b   c
word2:    p   q   r
merged: a p b q c r

    Example 2:

    Input: word1 = "ab", word2 = "pqrs"
Output: "apbqrs"
Explanation: Notice that as word2 is longer, "rs" is appended to the end.
word1:  a   b 
word2:    p   q   r   s
merged: a p b q   r   s

    Example 3:

    Input: word1 = "abcd", word2 = "pq"
Output: "apbqcd"
Explanation: Notice that as word1 is longer, "cd" is appended to the end.
word1:  a   b   c   d
word2:    p   q 
merged: a p b q c   d

    Constraints:

    • 1 <= word1.length, word2.length <= 100
    • word1 and word2 consist of lowercase English letters.

    This was my solution:

    class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        letters = []
        for index, letter in enumerate(word1):
            letters.append(letter)
            try:
                letters.append(word2[index])
            except IndexError:
                pass
        
        word1_size = len(word1)
        if len(word2) > word1_size:
            l = list(word2[word1_size:])
            letters.extend(l)

        return ''.join(letters)

    Continue practicing

    Browse the searchable 100 LeetCode Python Solutions interview study guide or download the complete tested solution library.

  • Leetcode 79 – Boggle Game / Word Search

    https://leetcode.com/problems/word-search/

    The link above is to the leetcode question. This problem set can be solved using backtracking and depth first search.

    The first thing to do when trying to understand these leetcode problems is to actually understand the problem and understand what it is asking you to do. So in this question, you are being asked to find out if a word is found on the game board. However, there are some restrictions.

    1. The word must be constructed with sequentially adjacent cells
    2. The cells may only be horizontally adjacent or vertically adjacent
    3. You cannot use the same letter cell twice

    So when we first think about this, we can think about the rule set. The third rule is a pretty big giveaway that we want to use a set. The set data structure allows you to only hold unique items.

    The first and second rule first makes me think that we are going to be using back tracking. Why? Because it is a situation where we can think of the solution as using a state space tree. We can also apply a bounding function which would restrict the certain “nodes” that we can search for. this would be the adjacent cells. Some pseudo code could look like this:

    x + 1, y
x - 1, y
x, y + 1
x, y - y

    These would be our four conditions for the different directions. We would also need to check and ensure that we are not going out of bounds of the game board.

    My final code solution was this:

    def word_found_in_board(board: list[list[str]], word: str) -> bool:
    rows = len(board)
    columns = len(board[0])
    path = set()

    def dfs(row: str, column: str, index: int):
        if index == len(word):
            return True
        if row < 0 or column < 0 or row >= rows or column >= columns or word[index] != board[row][column] or (row, column) in path:
            return False
        
        path.add((row, column))
        result = dfs(row + 1, column, index + 1) or dfs(row - 1, column, index + 1) or dfs(row, column + 1, index + 1) or dfs(row, column - 1, index + 1)
        path.remove((row, column))
        return result
    for row in range(rows):
        for column in range(columns):
            if dfs(row, column, 0):
                return True
    return False

    We get the length and width of the game board and call them “rows” and “columns”. Then we create a set called “path” which stores tuples. Each tuple is a row and column which meets the rules and requirements as stated above. Anything that meets the rules will be added to the “path” variable and then we recursively check each of the four adjacent positions.

    Continue practicing

    Browse the searchable 100 LeetCode Python Solutions interview study guide or download the complete tested solution library.

  • Leetcode 733 – FloodFill

    class Solution:
    
    def fill(self, image: List[List[int]], sr: int, sc: int, starting_color: int, newColor: int) -> List[List[int]]:
        if sr < 0 or sc < 0 or sr >= len(image) or sc >= len(image[0]) or image[sr][sc] != starting_color:
            return
        image[sr][sc] = newColor
        self.fill(image, sr + 1, sc, starting_color, newColor)
        self.fill(image, sr - 1, sc, starting_color, newColor)
        self.fill(image, sr, sc + 1, starting_color, newColor)
        self.fill(image, sr, sc - 1, starting_color, newColor)
        
    
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        if image[sr][sc] == newColor:
            return image
        self.fill(image, sr, sc, image[sr][sc], newColor)
        return image

    This is my solution for the flood fill problem in python.

    https://leetcode.com/problems/flood-fill/

    Continue practicing

    Browse the searchable 100 LeetCode Python Solutions interview study guide or download the complete tested solution library.