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 anywherefrom T) results in the string S.)
Example 1:
Input: str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation:
str1 = "abac" is a substring of "cabac" because we can delete the first "c".
str2 = "cab" is a substring of "cabac" because we can delete the last "ac".
The answer provided is the shortest such string that satisfies these properties.
Note:
1 <= str1.length, str2.length <= 1000
str1 and str2 consist of lowercase English letters.
Solution: LCS
Find the LCS (longest common sub-sequence) of two strings, and insert unmatched characters into the LCS.
There are n different online courses numbered from 1 to n. Each course has some duration(course length) t and closed on dth day. A course should be taken continuouslyfor t days and must be finished before or on the dth day. You will start at the 1st day.
Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken.
Example:
Input: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
Output: 3
Explanation:
There're totally 4 courses, but you can take 3 courses at most:
First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.
Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day.
Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day.
The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.
Note:
The integer 1 <= d, t, n <= 10,000.
You can’t take two courses simultaneously.
Solution: Priority queue
Sort courses by end date
Use a priority queue (Max-Heap) to store the course lengths or far
Swap with a longer course if we could not take the current one
Time complexity: O(nlogn) Space complexity: O(n)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Author: Huahua, running time: 196 ms, 40.5 MB
classSolution{
public:
intscheduleCourse(vector<vector<int>>& courses) {
sort(begin(courses), end(courses), [](const auto& a, const auto& b) {
There are N piles of stones arranged in a row. The i-th pile has stones[i] stones.
A move consists of merging exactly K consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these K piles.
Find the minimum cost to merge all piles of stones into one pile. If it is impossible, return -1.
Example 1:
Input: stones = [3,2,4,1], K = 2
Output: 20
Explanation:
We start with [3, 2, 4, 1].
We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].
We merge [4, 1] for a cost of 5, and we are left with [5, 5].
We merge [5, 5] for a cost of 10, and we are left with [10].
The total cost was 20, and this is the minimum possible.
Example 2:
Input: stones = [3,2,4,1], K = 3
Output: -1
Explanation: After any merge operation, there are 2 piles left, and we can't merge anymore. So the task is impossible.
Example 3:
Input: stones = [3,5,1,2,6], K = 3
Output: 25
Explanation:
We start with [3, 5, 1, 2, 6].
We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6].
We merge [3, 8, 6] for a cost of 17, and we are left with [17].
The total cost was 25, and this is the minimum possible.
Note:
1 <= stones.length <= 30
2 <= K <= 30
1 <= stones[i] <= 100
Solution: DP
dp[i][j][k] := min cost to merge subarray i ~ j into k piles Init: dp[i][j][k] = 0 if i==j and k == 1 else inf ans: dp[0][n-1][1] transition: 1. dp[i][j][k] = min{dp[i][m][1] + dp[m+1][j][k-1]} for all i <= m < j 2. dp[i][j][1] = dp[i][j][K] + sum(A[i]~A[j])
Time complexity: O(n^3) Space complexity: O(n^2*K)
C++
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
// Running time: 12 ms, 12.1 MB
classSolution{
public:
intmergeStones(vector<int>& stones, int K) {
const int n = stones.size();
if((n-1)%(K-1))return-1;
constintkInf=1e9;
vector<int>sums(n+1);
for(inti=0;i<stones.size();++i)
sums[i+1]=sums[i]+stones[i];
// dp[i][j][k] := min cost to merge subarray i~j into k piles.
std::function<int(int,int,int)>dp=[&stones, &sums, &cache, kInf, n, K, &dp](int i, int j, int k) {
if ((j - i + 1 - k) % (K - 1)) return kInf;
if(i==j)returnk==1?0:kInf;
if(cache[i][j][k]!=INT_MAX)returncache[i][j][k];
if(k==1)
returncache[i][j][k]=dp(i,j,K)+sums[j+1]-sums[i];
intans=kInf;
for(intm=i;m<j;m+=K-1){
intl=dp(i,m,1);
if(l>=ans)continue;
intr=dp(m+1,j,k-1);
if(r>=ans)continue;
ans=min(ans,l+r);
}
returncache[i][j][k]=ans;
};
returndp(0,n-1,1);
}
};
Solution 2: DP
dp[l][i] := min cost to merge [i, i + l) into as less piles as possible. Number of merges will be (l-1) / (K – 1) and Transition: dp[l][i] = min(dp[m][i] + dp[l – m][i + m]) for 1 <= m < l if ((l – 1) % (K – 1) == 0) [i, i + l) can be merged into 1 pile, dp[l][i] += sum(A[i:i+l])
Time complexity: O(n^3 / k) Space complexity: O(n^2)
C++
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
// Author: Huahua 4ms, 9.6 MB
classSolution{
public:
intmergeStones(vector<int>& stones, int K) {
const int n = stones.size();
if((n-1)%(K-1))return-1;
vector<int>sums(n+1);
for(inti=0;i<stones.size();++i)
sums[i+1]=sums[i]+stones[i];
constintkInf=1e9;
// dp[i][j] := min cost to merge subarray A[i] ~ A[j] into (j-i)%(K-1) + 1 piles
vector<vector<int>>dp(n,vector<int>(n,kInf));
for(inti=0;i<n;++i)dp[i][i]=0;
for(intl=2;l<=n;++l)// subproblem length
for(inti=0;i<=n-l;++i){// start
intj=i+l-1;
for(intm=i;m<j;m+=K-1)// split point
dp[i][j]=min(dp[i][j],dp[i][m]+dp[m+1][j]);
// If the current length can be merged into 1 pile
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in sthat is a concatenation of each word in words exactly once and without any intervening characters.
Example 1:
Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output:[0,9]Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.
Example 2:
Input:
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
Output:[]
Solution1: HashTable + Brute Force
Time complexity: O((|S| – |W|*l) * |W|*l)) Space complexity: O(|W|*l)
