adamfallon.com

Surprising solutions to Leetcode questions

Work in Progress - Will continue to update this as I find more

Here are some solutions to Leetcode questions that are non-obvious.

1. Finding maximum path in a matrix using depth first search

Question on LeetCode

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed). long-path.jpg

If is possible to traverse a path through a matrix to find the longest path using Depth First Search.

Let's go through it step by step, first the function signature, nothing fancy - takes a matrix.

def longestIncreasingPath(matrix): 

Next we want to create a local ref to the max row (m) and the max col (n).

This enables us to deal with misshapen matrices

m, n = len(matrix), len(matrix[0])

Next we write a depth first search function, just going to define it inline. First the function signature;

  • row position
  • column position
  • the previous value
  • visited (we can memoize some paths)
def dfs(i, j, prev, visited):

Next some edge case handling.

Firstly we can't;

  • move up (we can't go to row -= 1 if current row is 0)
  • down (row += 1 if we are at the last row in the matrix)
  • left (column -= 1 if we are at column 0)
  • right (column += 1 if we are the last column)
if not 0<=i<m or not 0<=j<n:return 0

Next we don't want to continue going down a path where the next value is less than the previous one.

For example say we have a matrix like this and are at matrix position 1,2 (which is the value 8) going down won't take us on the longest path because the value down in the path is 1, less than 8.

9 9 4
6 6 8
2 1 1

This edge case looks like this;

if matrix[i][j]<=prev: return 0

The last edge case isn't an edge case, we want to use our memoized paths we come across before. That way we don't recompute any path we've travelled on before.

if (i,j) in visited: return visited[(i,j)]

Okay all that out of the way it's time to recursively travel all the paths travelling in all the directions we can go (up, down, left, right). The edge cases we wrote above will allow us to return early and not waste time computing things we don't care about.

visited[(i, j)] = max(dfs(i-1,j, matrix[i][j], visited),\ 			<-- up
                      dfs(i+1, j, matrix[i][j], visited),\		<-- down
                      dfs(i, j-1, matrix[i][j], visited),\		<-- left
                      dfs(i, j+1, matrix[i][j], visited))+1		<-- right
return visited[(i, j)]

Okay now that is done we can call the dfs for each column and row

visited = {}
for i in range(m):
    for j in range(n):
        if(i,j) in visited:continue
        dfs(i, j, float("-inf"), visited)

And when that is all done, we can just grab the max value from the visited cache and we have our answer.

return max(visited.values())

Full code;

def longestIncreasingPath(matrix):
    m, n = len(matrix), len(matrix[0])

    def dfs(i, j, prev, visited):
        # If you can't move up or down in the rows (0<=i<m)
        # Or if you can't move left or right in the columns (0<=j<n)
        if not 0<=i<m or not 0<=j<n: return 0
        # If the next value is less than or equal to the previous value, we are at the end of the path
        if matrix[i][j]<=prev: return 0
        # If we've already visited the column and row then use the memoized path
        if(i, j) in visited: return visited[(i, j)]

        visited[(i, j)] = max(dfs(i-1,j, matrix[i][j], visited),\
                              dfs(i+1, j, matrix[i][j], visited),\
                              dfs(i, j-1, matrix[i][j], visited),\
                              dfs(i, j+1, matrix[i][j], visited))+1

        print(visited)
        return visited[(i, j)]

    visited = {}
    for i in range(m):
        for j in range(n):
            if(i,j) in visited:continue
            dfs(i, j, float("-inf"), visited)

    return max(visited.values())

2. Buddy Strings without iterating through and manually altering strings

Given two strings s and goal, return true if you can swap two letters in s so the result is equal to goal, otherwise, return false.

Swapping letters is defined as taking two indices i and j (0-indexed) such that i != j and swapping the characters at s[i] and s[j].

https://leetcode.com/problems/buddy-strings/

def buddyString(s, goal):
  # Not possible to create the same string without adding or subtracting characters which isn't allowed. 
  if len(s) != len(goal): return False
  # If s and goal match, and 
  if s == goal and len(set(s)) < len(s): return True
  # Create pairs of a,b from s and goal where a does not match b
  delta = [(a, b) for a, b in zip(s, goal) if a != b]
  # If the total difference equal 2 that means we can do a single swap
  # and if the first pair matches the second pair (which is reversed to show we can do the swap)
  return len(delta) == 2 and delta[0] == delta[1][::-1]

3. Finding if two strings are similar using a stack

Question on Leetcode

Surprsingly the following question can be solved using no additional memory other than a stack for the two sentences.

A sentence is a list of words that are separated by a single space with no leading or trailing spaces. For example, "Hello World", "HELLO", "hello world hello world" are all sentences. Words consist of only uppercase and lowercase English letters.

Two sentences sentence1 and sentence2 are similar if it is possible to insert an arbitrary sentence (possibly empty) inside one of these sentences such that the two sentences become equal. For example, sentence1 = "Hello my name is Jane" and sentence2 = "Hello Jane" can be made equal by inserting "my name is" between "Hello" and "Jane" in sentence2.

Given two sentences sentence1 and sentence2, return true if sentence1 and sentence2 are similar. Otherwise, return false.

def areSentencesSimilar(sentence1, sentence2):
    s1 = sentence1.split()
    s2 = sentence2.split()

    if len(s1)>len(s2):
        # swap values because we want the smaller string to be s1 as it is the one we are while'ing on, whereas s2 acts as the prefix and suffix
        s1, s2 = s2, s1

    # while we still have some words in s1
    while(s1):
        if s2[0] == s1[0]: # if the first word of each sentence match, pop
            s2.pop(0)
            s1.pop(0)
        elif s2[-1]==s1[-1]: # if the last word of each sentence match, pop
            s2.pop()
            s1.pop()
        else: # else we've come across a word that doesn't fit in the stream where s2s first and last words act as a prefix, suffix
            return False

    return True

print(areSentencesSimilar("My name is Haley", "My name"))
print(areSentencesSimilar("Eating right now", "Eating"))
print(areSentencesSimilar("of", "A lot of words")) 
print(areSentencesSimilar("CwFfRo regR", "CwFfRo H regR"))

Author: Adam Fallon

Created: 2022-01-05 Wed 23:27

Validate