Package Dependencies

Solution def package_dependencies(dependencies): result = [] visiting = set([]) visited = set([]) def dfs(node): if node in visited: return visiting.add(node) for dependency in node.dependencies: if dependency in visiting: raise Exception("Have cycle in dependency graph.") if dependency not in visited: dfs(dependency) for node in dependencies: dfs(node) visiting.remove(node) visited.add(node) result.add(add)

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

Concatenated Words

Given a list of words (without duplicates), please write a program that returns all concatenated words in the given list of words. A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array. Example: Input: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"] Output: ["catsdogcats","dogcatsdog","ratcatdogcat"] Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; "dogcatsdog" can be concatenated by "dog", "cats" and "dog"; "ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

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

Concatenate String Using Smaller Strings

Given a big string and a list of small strings, find whether the big string can be represented only by concatenation of smaller strings. Example: target = "abccbacbb" smallerStrings = ["abc", "cc", "ab", "bac", "b"] Output: True Solution Dynamic programming target = "abccbacbb" smallerStrings = ["abc", "cc", "ab", "bac", "b"] N = len(target) dp = [False for _ in range(N)] def check(i, target): for s in smallerStrings: l = len(s) # print(s) if i + l <= N: tryStr = target[i:i+l] # print(tryStr) if tryStr == s: dp[i+l-1] = True check(i+l, target) # print("-------") check(0, target) print(dp) print(dp[N-1])

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

Word Ladder Ii

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that: 1. Only one letter can be changed at a time 2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word. Note: Return an empty list if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters.

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

Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. Example 1: Input: "(()" Output: 2 Explanation: The longest valid parentheses substring is "()" Example 2: Input: ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()" Solution Dynamic programming // Time: O(n) // Space: O(n) public class Solution { public int longestValidParentheses(String s) { int maxans = 0; // dp array: ith element of dp represents the length of the longest valid substring ending at ith index.

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

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum. Note: A leaf is a node with no children. Example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 Return: [ [5,4,11,2], [5,8,4,5] ] Solution # Definition for a binary tree node.

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

Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again). Example 1: Input: [3,3,5,0,0,3,1,4] Output: 6 Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

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

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. *### Example 1 Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. *### Example 2 Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. *### Example 3 Input: "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

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

Min Cost Climbing Stairs

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed). Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1. Example 1: Input: cost = [10, 15, 20] Output: 15 Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

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

Reorder Data in Log Files

You have an array of logs. Each log is a space delimited string of words. For each log, the first word in each log is an alphanumeric identifier. Then, either: Each word after the identifier will consist only of lowercase letters, or; Each word after the identifier will consist only of digits. We will call these two varieties of logs letter-logs and digit-logs. It is guaranteed that each log has at least one word after its identifier.

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