LintCode (119) Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Have you met this question in a real interview? 

Yes

Example

Given word1 = "mart" and word2 = "karma", return 3.

首先这是一道dp题目，两个串，干个啥，求最小。

然后要搞清楚三个操作：

插入和删除： f[i-1][j], f[i][j-1] +1

替换： f[i-1][j-1]+1

或者无操作 f[i-1][j-1]

这样就变成了之前的longest subsequence的题目了，

其实你想想就是这样的，longest subsequence不就是找找那些一样的么。。。那么这三种操作完全可以把longest subsequence变成全串儿。。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

class Solution { public: /** * @param word1 & word2: Two string. * @return: The minimum number of steps. */ int minDistance(string word1, string word2) { // write your code here int m=word1.size(); int n=word2.size(); vector< vector<int> > f(m+1, vector<int>(n+1,0)); for (int i=1; i<=m; i++){ f[i][0]=i; } for (int j=1; j<=n; j++){ f[0][j]=j; } for (int i=1; i<=m; i++){ for (int j=1; j<=n; j++){ f[i][j]=min(f[i-1][j],f[i][j-1])+1; f[i][j]=min(f[i][j], word1[i-1]==word2[j-1]? f[i-1][j-1]: f[i-1][j-1]+1); } } return f[m][n]; } };

LintCode (79) Longest Common Substring Show result

Given two strings, find the longest common substring.

Return the length of it.

Have you met this question in a real interview? 

Yes

Example

Given A = "ABCD", B = "CBCE", return 2.

Note

The characters in substring should occur continuously in original string. This is different with subsequence.

Challenge

O(n x m) time and memory.

这玩意一看就是2D dp,两个串，比比求最长啥啥啥。。。和LCS不一样的是这玩意求得是连续的，所以根本不用管f[i][j-1]和f[i-1][j]， 裸扫一遍完事

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution { public: /** * @param A, B: Two string. * @return: the length of the longest common substring. */ int longestCommonSubstring(string &A, string &B) { // write your code here int m=A.size(); int n=B.size(); if (m==0 || n==0) return 0; vector< vector<int> > f(m+1, vector<int>(n+1, 0)); int result= INT_MIN; for (int i=1; i<=m; i++){ for (int j=1; j<=n; j++){ if (A[i-1]==B[j-1]) f[i][j]=f[i-1][j-1]+1; result=max(result, f[i][j]); } } return result; } };

LintCode (77) Longest Common Subsequence

Given two strings, find the longest common subsequence (LCS).

Your code should return the length of LCS.

Have you met this question in a real interview? 

Yes

Example

For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.

For "ABCD" and "EACB", the LCS is "AC", return 2.

Clarification

What's the definition of Longest Common Subsequence?

• https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
• http://baike.baidu.com/view/2020307.htm

属于二维dp， 

f[i][j]为 A的[0,i] 和B的[0,j]的LCS是多少

转移方程为 如果不等 max(f[i][j-1], f[i-1][j]), 如果相等， f[i-1][j-1]+1,其实这里有点贪婪的感觉，所以我觉得

max(f[i-1][j-1]）不等的时候和max(f[i-1][j-1]+1)反倒更明白些，速度话说快了一点点。。哈哈哈

再就是我做DP的和string相关的题目的时候总是犯一个低级错误，因为需要考虑空string的情况，dp 的函数总是多开一位，但是遍历string的时候就需要记得减掉一位，每次都犯错。。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: /** * @param A, B: Two strings. * @return: The length of longest common subsequence of A and B. */ int longestCommonSubsequence(string A, string B) { // write your code here int m = A.size(); int n = B.size(); vector< vector<int> > f(m+1, vector<int>(n+1, 0)); for (int i=1; i<=m; i++){ for (int j=1; j<=n; j++){ f[i][j]=max(f[i-1][j], f[i][j-1]); f[i][j]=max(f[i][j],A[i-1]==B[j-1]? f[i-1][j-1]+1: f[i-1][j-1]); } } return f[m][n]; } };

lintCode (76) Longest Increasing Subsequence

Given a sequence of integers, find the longest increasing subsequence (LIS).

You code should return the length of the LIS.

Have you met this question in a real interview? 

Yes

Example

For [5, 4, 1, 2, 3], the LIS  is [1, 2, 3], return 3

For [4, 2, 4, 5, 3, 7], the LIS is [4, 4, 5, 7], return 4

Challenge

Time complexity O(n^2) or O(nlogn)

Clarification

What's the definition of longest increasing subsequence?

    * The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.  

    * https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

f[i] = 0 to i max subsequence

initial state f[0]=1

update: f[i] = max(f[j] if a[j]<=a[i]) +1

result: max(f[i])

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

class Solution { public: /** * @param nums: The integer array * @return: The length of LIS (longest increasing subsequence) */ int longestIncreasingSubsequence(vector<int> nums) { // write your code here int n=nums.size(); if (n==0) return 0; vector<int> tbl(n, 1); for (int i=1; i<n; i++){ int val=INT_MIN; for(int j=0; j<i; j++){ if (nums[i]>=nums[j]) val=max(val, tbl[j]); } if (val!=INT_MIN) tbl[i]=val+1; } int result=INT_MIN; for (int i=0; i<n; i++){ result=max(result, tbl[i]); } return result; } };

LintCode (108) Palindrome Partitioning II

Given a string s, cut s into some substrings such that every substring is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Have you met this question in a real interview? 

Yes

Example

For example, given s = "aab",

Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

又是一道TLE的。。。，先写一个能过小数据的，分析一下再优化

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

class Solution { public: /** * @param s a string * @return an integer */ int minCut(string s) { // write your code here int n=s.size(); vector<int> tbl(n+1, INT_MAX); tbl[0]=0; for (int i=1; i<=n; i++){ int val=INT_MAX; for (int j=0; j<i; j++){ if (tbl[j]!=INT_MAX && isPalindrome(s.substr(j, i-j))){ val=min(val,tbl[j]); } tbl[i]=val+1; } } return tbl[n]-1; } bool isPalindrome(const string& s){ int b=0; int e=s.size()-1; while(b<e){ if (s[b++]!=s[e--]) return false; } return true; } };

计算一下有几个palindrome, f[i]为从0 到i的 p串数目， 那么最后cut为f[n]-1.  因为cut么。。。
复杂度是 o(n^3) 因为判断是不是p串是o(n).

一般这种一纬dp，复杂度就是o(n^2)撑死了，除了像爬楼梯那种o(n)的很少见。 所以要过大数据就在判断是不是p串上做手脚。。。

判断一个字符串从i到j其实做了很多重复工作， build一个table。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

class Solution { public: /** * @param s a string * @return an integer */ int minCut(string s) { // write your code here int n=s.size(); vector<int> tbl(n+1, INT_MAX); tbl[0]=0; vector<vector<bool>> ptbl(n, vector<bool>(n, false)); buildPTable(ptbl, s); for (int i=1; i<=n; i++){ int val=INT_MAX; for (int j=0; j<i; j++){ if (tbl[j]!=INT_MAX && ptbl[j][i-1]){ val=min(val,tbl[j]); } tbl[i]=val+1; } } return tbl[n]-1; } void buildPTable(vector<vector<bool>>& ptbl, const string& s){ //f[i][j] means from i to j, is p string // initial condition int n=s.size(); for (int i=0; i<n; i++) ptbl[i][i]=true; for (int i=0; i<n-1; i++) ptbl[i][i+1]=s[i] == s[i+1]; for (int len=2; len<n; len++){ for (int b=0; b+len<n; b++){ ptbl[b][b+len]=ptbl[b+1][b+len-1] && s[b]==s[b+len]; } } } };

其实buildTable本身比这个题目有趣一些：

f[i][j]为从i,到j是否为p string
初始条件 对角线上f[i][i]自然是true,因为只有一个字，再就是对角线平移一位，[i][i+1]比较一下，这样做的原因是"bb"这种case也算pstring...

转移方程： f[i][j]如果是true的话，当s[i-1]==s[j+1]的时候， f[i-1][j+1]=true, 反推：
f[i][j]= f[i+1][j-1] && s[i]=s[j]
这个遍历比较有趣，就是外面遍历长度差，从最小为2，一直到真个string,对于每一个长度，我们要选一个起始点，为从0开始来维持对称

其实这个buildTable真要考到我是一时半会想不出，要画一个table,装模作样的列几个例子，然后就开始默写了。。。lol

LintCode (107) Word Break

Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words.

Have you met this question in a real interview? 

Yes

Example

Given s = "lintcode", dict = ["lint", "code"].

Return true because "lintcode" can be break as "lint code".

又是TLE。。。o(n^2)...但是过不了大数据，TLE了。。。先贴个简单的，再仔细分析怎么弄吧。。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution { public: /** * @param s: A string s * @param dict: A dictionary of words dict */ bool wordBreak(string s, unordered_set<string> &dict) { // write your code here int n=s.size(); vector<bool> tbl(n+1, false); tbl[0]=true; for (int i=1; i<=n; i++){ for (int j=0; j<i; j++){ if (tbl[j] && dict.find(s.substr(j,i-j))!=dict.end()){ tbl[i]=true; break; } } } return tbl[n]; } };

简单的优化就是从后往前找，找到set里面最大的长度为止，这样复杂度就变成o(n,max(string.size())了。。。蛋疼。。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

class Solution { public: /** * @param s: A string s * @param dict: A dictionary of words dict */ bool wordBreak(string s, unordered_set<string> &dict) { // write your code here int n=s.size(); vector<bool> tbl(n+1, false); tbl[0]=true; int maxLen=getMaxLength(dict); for (int i=1; i<=n; i++){ for (int j=i-1; j>=0 && j>=i-maxLen; j--){ if (tbl[j] && dict.find(s.substr(j,i-j))!=dict.end()){ tbl[i]=true; break; } } } return tbl[n]; } int getMaxLength(unordered_set<string> &dict){ unordered_set<string>::iterator it=dict.begin(); int len=INT_MIN; for(;it!=dict.end();++it){ len= max(len, (int)(*it).size()); } return len; } };

lintCode (117) Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Have you met this question in a real interview? 

Yes

Example

Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

这题是哥白撕不得其姐的一道题。。。总是LTE， 事实上用了一个DP+贪婪，每次碰上贪婪哥就跪了，这个题目的贪婪在于，他认为越早发现能调到当前位置，那么步数就越少， 感觉很有道理的样子，但是实际是又说不出道理，哥只能妥协，为了过test case...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution { public: /** * @param A: A list of lists of integers * @return: An integer */ int jump(vector<int> A) { // wirte your code here int n = A.size(); if (n==0 || A[0]==0) return 0; vector<int> tbl(n, INT_MAX); tbl[0]=0; for (int i=1 ; i<n ; i++){ for (int j=0; j<i; j++){ if (tbl[j]!=INT_MAX && j+A[j]>=i){ tbl[i]=tbl[j]+1; break; } } } return tbl[n-1]; } };