# Daily Coding Challenge #16

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.

``````/*
LeetCode - Uncrossed Lines

We write the integers of A and B (in the order they are given) on two separate horizontal lines.

Now, we may draw connecting lines: a straight line connecting two numbers A[i] and B[j] such that:

A[i] == B[j];
The line we draw does not intersect any other connecting (non-horizontal) line.
Note that a connecting lines cannot intersect even at the endpoints: each number can only belong to one connecting line.

Return the maximum number of connecting lines we can draw in this way.

Example 1:

Input: A = [1,4,2], B = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from A[1]=4 to B[2]=4 will intersect the line from A[2]=2 to B[1]=2.
Example 2:

Input: A = [2,5,1,2,5], B = [10,5,2,1,5,2]
Output: 3
Example 3:

Input: A = [1,3,7,1,7,5], B = [1,9,2,5,1]
Output: 2

Note:

1 <= A.length <= 500
1 <= B.length <= 500
1 <= A[i], B[i] <= 2000
*/

class Solution {
public:
int maxUncrossedLines(vector<int>& A, vector<int>& B) {
// typical longest common subsequence problem
int m=A.size(),n=B.size();
int dp[m+1][n+1];
memset(dp,0,sizeof(dp));
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(A[i-1]==B[j-1]){
// if the integers are same, take top left value plus one
dp[i][j]=1+dp[i-1][j-1];
} else {
// if not, take the max value from the left or the top value
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[m][n];
}
};
``````

``````/*
LeetCode - 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')
*/

class Solution {
public:
int minDistance(string word1, string word2) {
int m=word1.size(),n=word2.size();
int dp[m+1][n+1];
memset(dp,0,sizeof(dp));
for(int i=1;i<=m;i++) dp[i][0]=i;
for(int j=1;j<=n;j++) dp[0][j]=j;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(word1[i-1]==word2[j-1]){ // a=b
dp[i][j]=dp[i-1][j-1];
} else {
// find out the min cost for all three actions
dp[i][j] = 1+min({
dp[i-1][j-1], //replace a with b
dp[i-1][j], // delete a
dp[i][j-1] // insert b after a
});
}
}
}
return dp[m][n];
}
};
``````

``````/*
LeetCode - Delete Operation for Two Strings

Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.

Example 1:
Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
Note:
The length of given words won't exceed 500.
Characters in given words can only be lower-case letters.
*/

class Solution {
public:
int minDistance(string word1, string word2) {
int m=word1.size(),n=word2.size();
int dp[m+1][n+1];
memset(dp,0,sizeof(dp));
for(int i=1;i<=m;i++) dp[i][0]=i;
for(int j=1;j<=n;j++) dp[0][j]=j;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(word1[i-1]==word2[j-1]){
dp[i][j]=dp[i-1][j-1];
} else {
// delete a character in word1 or delete a character in word2
// pick the min cost
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;
}
}
}
return dp[m][n];
}
};
``````

``````/*
LeetCode - Longest Palindromic Subsequence

Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:

"bbbab"
Output:
4
One possible longest palindromic subsequence is "bbbb".
Example 2:
Input:

"cbbd"
Output:
2
One possible longest palindromic subsequence is "bb".
*/

class Solution {
public:
int longestPalindromeSubseq(string s) {
// if we reverse s as t, given string s and t, this is a typical LCS problem
string t=s;
reverse(t.begin(),t.end());
int m=s.size(),n=t.size();
int dp[m+1][n+1];
memset(dp,0,sizeof(dp));
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(s[i-1]==t[j-1]){
dp[i][j]=1+dp[i-1][j-1];
}else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[m][n];
}
};
``````

The source code is available in corresponding repo below. Star and watch for timely updates!

## wingkwong / atcoder

Posted on by:

### Wing-Kam

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.