Paint House II

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on… Find the minimum cost to paint all houses.

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

Paint House

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.

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

Longest Bitonic Subsequence

Given an array arr[0 … n-1] containing n positive integers, a subsequence of arr[] is called Bitonic if it is first increasing, then decreasing. Write a function that takes an array as argument and returns the length of the longest bitonic subsequence. A sequence, sorted in increasing order is considered Bitonic with the decreasing part as empty. Similarly, decreasing order sequence is considered Bitonic with the increasing part as empty.

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

Decode Ways II

A message containing letters from A-Z is being encoded to numbers using the following mapping way: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers from 1 to 9. Given the encoded message containing digits and the character '*', return the total number of ways to decode it.

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

Shortest Common Supersequence

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If multiple answers exist, you may return any of them. (A string S is a subsequence of string T if deleting some number of characters from T (possibly 0, and the characters are chosen anywhere from T) results in the string S.) Example 1 Input: str1 = "abac", str2 = "cab" Output: "cabac" Explanation: str1 = "abac" is a subsequence of "cabac" because we can delete the first "c".

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

Longest Common Substring

Solution: public class LongestCommonString { /* Returns length of LCS for X[0..m-1], Y[0..n-1] */ int lcs( char[] X, char[] Y, int m, int n ) { // Size = m + 1, n + 1. int L[][] = new int[m+1][n+1]; Integer result = Integer.MIN_VALUE; /* Following steps build L[m+1][n+1] in bottom up fashion. Note ** that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */ for (int i=0; i<=m; i++) { for (int j=0; j<=n; j++) { if (i == 0 || j == 0) // Initialise L[0][0] = 0 L[i][j] = 0; else if (X[i-1] == Y[j-1]) // L[1][1] = L[0][0] + 1 = 0 + 1 = 1 L[i][j] = L[i-1][j-1] + 1; else L[i][j] = 0; if (dp[i][j] > result) { result = dp[i][j]; } } } return result; }

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

Greatest Sum Divisible by Three

Given an array nums of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three. Example 1 Input: nums = [3,6,5,1,8] Output: 18 Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3). Example 2 Input: nums = [4] Output: 0 Explanation: Since 4 is not divisible by 3, do not pick any number.

by lek tin in "algorithm" access_time 2-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

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