Posts tagged as “dp”

花花酱 LeetCode 1092. Shortest Common Supersequence

By zxi on June 16, 2019

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.

Time complexity: O(mn)
Space complexity: O(mn)

C++

// Author: Huahua, running time: 16 ms, 15.3 MB

class Solution {

public:

string shortestCommonSupersequence(string str1, string str2) {

int l1 = str1.length();

int l2 = str2.length();

vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1));

for (int i = 1; i <= l1; ++i)

for (int j = 1; j <= l2; ++j)

dp[i][j] = str1[i - 1] == str2[j - 1] ?

1 + dp[i - 1][j - 1] :

max(dp[i - 1][j], dp[i][j - 1]);

deque<char> ans;

while (l1 || l2) {

char c;

if (l1 == 0) c = str2[--l2];

else if (l2 == 0) c = str1[--l1];

else if (str1[l1 - 1] == str2[l2 - 1]) c = str1[--l1] = str2[--l2];

else if (dp[l1 - 1][l2] == dp[l1][l2]) c = str1[--l1];

else if (dp[l1][l2 - 1] == dp[l1][l2]) c = str2[--l2];

ans.push_front(c);

}

return {begin(ans), end(ans)};

}

};

花花酱 LeetCode Weekly Contest 137

By zxi on May 18, 2019

1046. Last Stone Weight

Solution: Simulation (priority_queue)

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int lastStoneWeight(vector<int>& stones) {

priority_queue<int> q;

for (int s : stones)

q.push(s);

while (q.size() > 1) {

int x = q.top(); q.pop();

int y = q.top(); q.pop();

if (x == y) continue;

q.push(abs(x - y));

}

return q.empty() ? 0 : q.top();

}

};

1047. Remove All Adjacent Duplicates In String

Solution: Stack / Deque

Time complexity: O(n)
Space complexity: O(n)

C++

class Solution {

public:

string removeDuplicates(string S) {

deque<char> s;

for (char c : S) {

if (!s.empty() && s.back() == c) s.pop_back();

else s.push_back(c);

}

return {begin(s), end(s)};

}

};

1048. Longest String Chain

Solution: DP

dp[i] := max length of chain of (A[0] ~ A[i-1])

dp[i] = max{dp[j] + 1} if A[j] is prederrsor of A[i], 1 <= j <i

Time complexity: O(n^2*l)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int longestStrChain(vector<string>& words) {

int n = words.size();

sort(begin(words), end(words), [](const string& a, const string& b) {

return a.length() < b.length();

});

vector<int> dp(n, 1);

for (int i = 0; i < n; ++i)

for (int j = 0; j < i; ++j)

if (valid(words[j], words[i]))

dp[i] = dp[j] + 1;

return *max_element(begin(dp), end(dp));

}

private:

bool valid(const string& a, const string& b) {

if (a.length() + 1 != b.length()) return false;

int count = 0;

for (int i = 0, j = 0; i < a.length() && j < b.length();) {

if (a[i] == b[j]) {

++i; ++j;

} else {

++count; ++j;

}

return count <= 1;

}

};

1049. Last Stone Weight II

Solution: DP / target sum

Time complexity: O(n * S) = O(n * 100)

Space complexity: O(S) = O(100)

C++

// Author: Huahua

class Solution {

public:

int lastStoneWeightII(vector<int>& stones) {

const int n = stones.size();

const int max_sum = accumulate(begin(stones), end(stones), 0);

unordered_set<int> sums;

sums.insert(stones[0]);

sums.insert(-stones[0]);

for (int i = 1; i < n; ++i) {

unordered_set<int> tmp;

for (int s : sums) {

tmp.insert(s + stones[i]);

tmp.insert(s - stones[i]);

}

swap(tmp, sums);

}

int ans = INT_MAX;

for (int s : sums)

ans = min(ans, abs(s));

return ans;

}

};

花花酱 LeetCode 718. Maximum Length of Repeated Subarray

By zxi on May 17, 2019

iven two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

Example 1:

Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation: 
The repeated subarray with maximum length is [3, 2, 1].

Note:

1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

Solution: DP

dp[i][j] := max length of (A[0:i], B[0:j])

dp[i][j] = dp[i – 1][j – 1] + 1 if A[i-1] == B[j-1] else 0

Time complexity: O(m*n)
Space complexity: O(m*n) -> O(n)

C++ S:O(mn)

// Author: Huahua, 176 ms / 106.4 MB

class Solution {

public:

int findLength(vector<int>& A, vector<int>& B) {

int m = A.size();

int n = B.size();

vector<vector<int>> dp(m + 1, vector<int>(n + 1));

int ans = 0;

for (int i = 1; i <= m; ++i)

for (int j = 1; j <= n; ++j)

if (A[i - 1] == B[j - 1]) {

dp[i][j] = dp[i - 1][j - 1] + 1;

ans = max(ans, dp[i][j]);

}

return ans;

}

};

C++ S:O(min(m,n))

// Author: Huahua, 152 ms / 9.1 MB

class Solution {

public:

int findLength(vector<int>& A, vector<int>& B) {

if (A.size() < B.size()) swap(A, B);

int m = A.size();

int n = B.size();

vector<int> dp(n + 1);

int ans = 0;

for (int i = 1; i <= m; ++i)

for (int j = n; j >= 1; --j) {

dp[j] = A[i - 1] == B[j - 1] ? dp[j - 1] + 1 : 0;

ans = max(ans, dp[j]);

}

return ans;

}

};

花花酱 LeetCode 1043. Partition Array for Maximum Sum

By zxi on May 14, 2019

Given an integer array A, you partition the array into (contiguous) subarrays of length at most K. After partitioning, each subarray has their values changed to become the maximum value of that subarray.

Return the largest sum of the given array after partitioning.

Example 1:

Input: A = [1,15,7,9,2,5,10], K = 3
Output: 84
Explanation: A becomes [15,15,15,9,10,10,10]

Note:

1 <= K <= A.length <= 500
0 <= A[i] <= 10^6

Solution: DP

Time complexity: O(n*k)
Space complexity: O(n)

dp[i] := max sum of A[1] ~ A[i]
init: dp[0] = 0
transition: dp[i] = max{dp[i – k] + max(A[i-k:i]) * k}, 1 <= k <= min(i, K)
ans: dp[n]

A = | 2 | 1 | 4 | 3 |
K = 3
dp[0] = 0
dp[1] = max(dp[0] + 2 * 1) = 2
dp[2] = max(dp[0] + 2 * 2, dp[1] + 1 * 1) = max(4, 3) = 4
dp[3] = max(dp[0] + 4 * 3, dp[1] + 4 * 2, dp[2] + 4 * 1) = max(12, 10, 8) = 12
dp[4] = max(dp[1] + 4 * 3, dp[2] + 4 * 2, dp[3] + 3 * 1) = max(14, 12, 15) = 15
best = | 4 | 4 | 4 | 3 |

C++

class Solution {

public:

int maxSumAfterPartitioning(vector<int>& A, int K) {

int n = A.size();

vector<int> dp(n + 1, 0);

for (int i = 1; i <= n; ++i) {

int m = INT_MIN;

for (int k = 1; k <= K && i - k >= 0; ++k) {

m = max(m, A[i - k]);

dp[i] = max(dp[i], dp[i - k] + m * k);

}

return dp[n];

}

};

花花酱 LeetCode Weekly Contest 133

By zxi on April 20, 2019

LeetCode 1029 Two City Scheduling

Solution1: DP

dp[i][j] := min cost to put j people into city A for the first i people
dp[0][0] = 0
dp[i][0] = dp[i -1][0] + cost_b
dp[i][j] = min(dp[i – 1][j] + cost_b, dp[i – 1][j – 1] + cost_a)
ans := dp[n][n/2]

Time complexity: O(n^2)
Space complexity: O(n^2)

C++

// Author: Huahua, running time: 8 ms

class Solution {

public:

int twoCitySchedCost(vector<vector<int>>& costs) {

int n = costs.size();

vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MAX / 2));

dp[0][0] = 0;

for (int i = 1; i <= n; ++i) {

dp[i][0] = dp[i - 1][0] + costs[i - 1][1];

for (int j = 1; j <= i; ++j)

dp[i][j] = min(dp[i - 1][j - 1] + costs[i - 1][0],

dp[i - 1][j] + costs[i - 1][1]);

}

return dp[n][n / 2];

}

};

Solution 2: Greedy

Sort by cost_a – cost_b

Choose the first n/2 people for A, rest for B

Time complexity: O(nlogn)
Space complexity: O(1)

C++

// Author: Huahua, running time: 8 ms

class Solution {

public:

int twoCitySchedCost(vector<vector<int>>& costs) {

int n = costs.size();

sort(begin(costs), end(costs), [](const auto& c1, const auto& c2){

return c1[0] - c1[1] < c2[0] - c2[1];

});

int ans = 0;

for (int i = 0; i < n; ++i)

ans += i < n/2 ? costs[i][0] : costs[i][1];

return ans;

}

};

1030. Matrix Cells in Distance Order

Solution: Sorting

Time complexity: O(RC*log(RC))
Space complexity: O(RC)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {

vector<vector<int>> ans;

for (int i = 0; i < R; ++i)

for (int j = 0; j < C; ++j)

ans.push_back({i, j});

std::sort(begin(ans), end(ans), [r0, c0](const vector<int>& a, const vector<int>& b){

return (abs(a[0] - r0) + abs(a[1] - c0)) < (abs(b[0] - r0) + abs(b[1] - c0));

});

return ans;

}

};

1031. Maximum Sum of Two Non-Overlapping Subarrays

Solution: Prefix sum

Time complexity: O(n^2)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {

const int n = A.size();

vector<int> s(n + 1, 0);

for (int i = 0; i < n; ++i)

s[i + 1] = s[i] + A[i];

int ans = 0;

for (int i = 0; i <= n - L; ++i) {

int ls = s[i + L] - s[i];

int ms = max(maxSum(s, 0, i - M - 1, M),

maxSum(s, i + L, n - M, M));

ans = max(ans, ls + ms);

}

return ans;

}

private:

int maxSum(const vector<int>& s, int start, int end, int l) {

int ans = INT_MIN;

for (int i = start; i <= end; ++i)

ans = max(ans, s[i + l] - s[i]);

return ans;

}

};

1032. Stream of Characters

Solution: Trie

Time complexity:

build O(sum(len(w))
query O(max(len(w))

Space complexity: O(sum(len(w))

C++

// Author: Huahua, 320 ms, 95 MB

class TrieNode {

public:

~TrieNode() {

for (auto node : next_)

delete node;

}

void reverse_build(const string& s, int i) {

if (i == -1) {

is_word_ = true;

return;

}

const int idx = s[i] - 'a';

if (!next_[idx]) next_[idx] = new TrieNode();

next_[idx]->reverse_build(s, i - 1);

}

bool reverse_search(const string& s, int i) {

if (i == -1 || is_word_) return is_word_;

const int idx = s[i] - 'a';

if (!next_[idx]) return false;

return next_[idx]->reverse_search(s, i - 1);

}

private:

bool is_word_ = false;

TrieNode* next_[26] = {0};

};

class StreamChecker {

public:

StreamChecker(vector<string>& words) {

root_ = std::make_unique<TrieNode>();

for (const string& w : words)

root_->reverse_build(w, w.length() - 1);

}

bool query(char letter) {

s_ += letter;

return root_->reverse_search(s_, s_.length() - 1);

}

private:

string s_;

unique_ptr<TrieNode> root_;

};

Java

// Author: Huahua, running time: 133 ms

class StreamChecker {

class TrieNode {

public TrieNode() {

isWord = false;

next = new TrieNode[26];

}

public boolean isWord;

public TrieNode next[];

}

private TrieNode root;

private StringBuilder sb;

public StreamChecker(String[] words) {

root = new TrieNode();

sb = new StringBuilder();

for (String word : words) {

TrieNode node = root;

char[] w = word.toCharArray();

for (int i = w.length - 1; i >= 0; --i) {

int idx = w[i] - 'a';

if (node.next[idx] == null) node.next[idx] = new TrieNode();

node = node.next[idx];

}

node.isWord = true;

}

public boolean query(char letter) {

sb.append(letter);

TrieNode node = root;

for (int i = sb.length() - 1; i >= 0; --i) {

int idx = sb.charAt(i) - 'a';

if (node.next[idx] == null) return false;

if (node.next[idx].isWord) return true;

node = node.next[idx];

}

return false;

}