Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string “". Example 1 Input: ["flower","flow","flight"] Output: "fl" Example 2 Input: ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings. Note All given inputs are in lowercase letters a-z. Note # Time: O(n*l), l: number of strings class Solution(object): def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ if not strs or len(strs) == 0: return "" res = strs[0] for s in strs: # string.

by lek tin in "algorithm" access_time 1-min read

Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1 Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example 2 Input: "cbbd" Output: "bb" Solution Dynamic Programming # https://leetcode.com/problems/longest-palindromic-substring/discuss/157861/Python3-DP-Solution-with-Lots-of-Comments # time: O(n^2) # space: O(n^2) class Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: str """ str_len = len(s) if str_len == 0: return "" # Initialize DP table (dimensions: str_len x str_len) memo = [[False for i in range(str_len)] for j in range(str_len)] start = 0 # Starting index of the longest palindrome max_len = 1 # Length of the longest palindrome # Fill DP table for single char palindromes for i in range(str_len): memo[i][i] = True # Fill DP table for 2 char long palindromes for i in range(str_len - 1): j = i + 1 if s[i] == s[j]: memo[i][j] = True start = i max_len = 2 # Fill DP table for palindromes of every other length # starting from 3 for length in range(3, str_len + 1): for i in range(str_len - length + 1): j = i + (length - 1) if s[i] == s[j] and memo[i+1][j-1]: memo[i][j] = True start = i max_len = length return s[start: start + max_len] # time: O(n^2) # space: O(1) class Solution(object): def __init__(self): self.

by lek tin in "algorithm" access_time 2-min read

Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Example Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.

by lek tin in "algorithm" access_time 1-min read

Edit Distance

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word: Insert a character Delete a character Replace a character Example 1 Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') Example 2 Input: word1 = "intention", word2 = "execution" Output: 5 Explanation: intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u') Solution: class Solution { public int minDistance(String word1, String word2) { if (word1 == null || word2 == null) return -1; if (word1.

by lek tin in "algorithm" access_time 2-min read

Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer. Example 1 Input: 123 Output: 321 Example 2 Input: -123 Output: -321 Example 3 Input: 120 Output: 21 Note Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows. Solution class Solution(object): def reverse(self, x): """ :type x: int :rtype: int """ if x == "" or x == None: return x res = "" if x > 0 else "-" string = str(abs(x)) for i in range(len(string)-1, -1, -1): res += string[i] res = int(res) if res < -2**31 or res >= 2**31: return 0 return int(res) class Solution: def reverse(self, x: int) -> int: isNegative = x < 0 x = abs(x) new_x = 0 while x !

by lek tin in "algorithm" access_time 1-min read

One Edit Distance

Given two strings s and t, determine if they are both one edit distance apart. Note There are 3 possiblities to satisify one edit distance apart: Insert a character into s to get t Delete a character from s to get t Replace a character of s to get t Example 1 Input: s = "ab", t = "acb" Output: true Explanation: We can insert 'c' into s to get t.

by lek tin in "algorithm" access_time 2-min read

Find a Local Minima in an Array

Given an array arr[0 .. n-1] of distinct integers, the task is to find a local minima in it. We say that an element arr[x] is a local minimum if it is less than or equal to both its neighbors. For corner elements, we need to consider only one neighbor for comparison. There can be more than one local minima in an array, we need to find any one of them.

by lek tin in "algorithm" access_time 2-min read

Binary Tree Vertical Order Traversal

Given a binary tree, return the vertical order traversal of its nodes’ values. (ie, from top to bottom, column by column). If two nodes are in the same row and column, the order should be from left to right. Example 1 Input: [3,9,20,null,null,15,7] 3 /\ / \ 9 20 /\ / \ 15 7 Output: [ [9], [3,15], [20], [7] ] Example 2 Input: [3,9,8,4,0,1,7] 3 /\ / \ 9 8 /\ /\ / \/ \ 4 01 7 Output: [ [4], [9], [3,0,1], [8], [7] ] Example 3 Input: [3,9,8,4,0,1,7,null,null,null,2,5] (0's right child is 2 and 1's left child is 5) 3 /\ / \ 9 8 /\ /\ / \/ \ 4 01 7 /\ / \ 5 2 Output: [ [4], [9,5], [3,0,1], [8,2], [7] ] Solution # https://www.

by lek tin in "algorithm" access_time 2-min read

Convert Binary Search Tree to Sorted Doubly Linked List

Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list. Let’s take the following BST as an example, it may help you understand the problem better: We want to transform this BST into a circular doubly linked list. Each node in a doubly linked list has a predecessor and successor. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

by lek tin in "algorithm" access_time 2-min read

Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence. Example: Input: [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. Note There may be more than one LIS combination, it is only necessary for you to return the length. Your algorithm should run in O(n2) complexity. Follow up: Could you improve it to O(n log n) time complexity? Solution (Bottom-up) Python

by lek tin in "algorithm" access_time 2-min read