花花酱 LeetCode 943. Find the Shortest Superstring

By zxi on November 18, 2018

Problem

Given an array A of strings, find any smallest string that contains each string in A as a substring.

We may assume that no string in A is substring of another string in A.

Example 1:

Input: ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
Explanation: All permutations of "alex","loves","leetcode" would also be accepted.

Example 2:

Input: ["catg","ctaagt","gcta","ttca","atgcatc"]
Output: "gctaagttcatgcatc"

Note:

1 <= A.length <= 12
1 <= A[i].length <= 20

Solution 1: Search + Pruning

Try all permutations. Pre-process the cost from word[i] to word[j] and store it in g[i][j].

Time complexity: O(n!)

Space complexity: O(n)

C++

// Author: Huahua, running time: 692 ms

class Solution {

public:

string shortestSuperstring(vector<string>& A) {

const int n = A.size();

g_ = vector<vector<int>>(n, vector<int>(n));

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

for (int j = 0; j < n; ++j) {

g_[i][j] = A[j].length();

for (int k = 1; k <= min(A[i].length(), A[j].length()); ++k)

if (A[i].substr(A[i].size() - k) == A[j].substr(0, k))

g_[i][j] = A[j].length() - k;

}

vector<int> path(n);

best_len_ = INT_MAX;

dfs(A, 0, 0, 0, path);

string ans = A[best_path_[0]];

for (int k = 1; k < best_path_.size(); ++k) {

int i = best_path_[k - 1];

int j = best_path_[k];

ans += A[j].substr(A[j].length() - g_[i][j]);

}

return ans;

}

private:

vector<vector<int>> g_;

vector<int> best_path_;

int best_len_;

void dfs(const vector<string>& A, int d, int used, int cur_len, vector<int>& path) {

if (cur_len >= best_len_) return;

if (d == A.size()) {

best_len_ = cur_len;

best_path_ = path;

return;

}

for (int i = 0; i < A.size(); ++i) {

if (used & (1 << i)) continue;

path[d] = i;

dfs(A,

d + 1,

used | (1 << i),

d == 0 ? A[i].length() : cur_len + g_[path[d - 1]][i],

path);

}

};

Java

// Author: Huahua, 439 ms, 35.8MB

class Solution {

private int n;

private int[][] g;

private String[] a;

private int best_len;

private int[] path;

private int[] best_path;

private void dfs(int d, int used, int cur_len) {

if (cur_len >= best_len) return;

if (d == n) {

best_len = cur_len;

best_path = path.clone();

return;

}

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

if ((used & (1 << i)) != 0) continue;

path[d] = i;

dfs(d + 1,

used | (1 << i),

d == 0 ? a[i].length() : cur_len + g[path[d - 1]][i]);

}

public String shortestSuperstring(String[] A) {

n = A.length;

g = new int[n][n];

a = A;

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

for (int j = 0; j < n; ++j) {

g[i][j] = A[j].length();

for (int k = 1; k <= Math.min(A[i].length(), A[j].length()); ++k)

if (A[i].substring(A[i].length() - k).equals(A[j].substring(0, k)))

g[i][j] = A[j].length() - k;

}

path = new int[n];

best_len = Integer.MAX_VALUE;

dfs(0, 0, 0);

String ans = A[best_path[0]];

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

int i = best_path[k - 1];

int j = best_path[k];

ans += A[j].substring(A[j].length() - g[i][j]);

}

return ans;

}

Solution 2: DP

g[i][j] is the cost of appending word[j] after word[i], or weight of edge[i][j].

We would like find the shortest path to visit each node from 0 to n – 1 once and only once this is called the Travelling sells man’s problem which is NP-Complete.

We can solve it with DP that uses exponential time.

dp[s][i] := min distance to visit nodes (represented as a binary state s) once and only once and the path ends with node i.

e.g. dp[7][1] is the min distance to visit nodes (0, 1, 2) and ends with node 1, the possible paths could be (0, 2, 1), (2, 0, 1).

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

Space complexity: O(n * 2^n)

C++

// Author: Huahua, running time: 20 ms

class Solution {

public:

string shortestSuperstring(vector<string>& A) {

const int n = A.size();

vector<vector<int>> g(n, vector<int>(n));

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

for (int j = 0; j < n; ++j) {

g[i][j] = A[j].length();

for (int k = 1; k <= min(A[i].length(), A[j].length()); ++k)

if (A[i].substr(A[i].size() - k) == A[j].substr(0, k))

g[i][j] = A[j].length() - k;

}

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

vector<vector<int>> parent(1 << n, vector<int>(n, -1));

for (int i = 0; i < n; ++i) dp[1 << i][i] = A[i].length();

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

for (int j = 0; j < n; ++j) {

if (!(s & (1 << j))) continue;

int ps = s & ~(1 << j);

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

if (dp[ps][i] + g[i][j] < dp[s][j]) {

dp[s][j] = dp[ps][i] + g[i][j];

parent[s][j] = i;

}

auto it = min_element(begin(dp.back()), end(dp.back()));

int j = it - begin(dp.back());

int s = (1 << n) - 1;

string ans;

while (s) {

int i = parent[s][j];

if (i < 0) ans = A[j] + ans;

else ans = A[j].substr(A[j].length() - g[i][j]) + ans;

s &= ~(1 << j);

j = i;

}

return ans;

}

};

花花酱 LeetCode 944. Delete Columns to Make Sorted

By zxi on November 18, 2018

Problem

We are given an array A of N lowercase letter strings, all of the same length.

Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.

For example, if we have a string "abcdef" and deletion indices {0, 2, 3}, then the final string after deletion is "bef".

Suppose we chose a set of deletion indices D such that after deletions, each remaining column in A is in non-decreasing sorted order.

Formally, the c-th column is [A[0][c], A[1][c], ..., A[A.length-1][c]]

Return the minimum possible value of D.length.

Example 1:

Input: ["cba","daf","ghi"]
Output: 1

Example 2:

Input: ["a","b"]
Output: 0

Example 3:

Input: ["zyx","wvu","tsr"]
Output: 3

Note:

1 <= A.length <= 100
1 <= A[i].length <= 1000

Solution: Simulation

Check descending case column by column.

Time complexity: O(NL)

Space complexity: O(1)

C++

// Author: Huahua, 64 ms

class Solution {

public:

int minDeletionSize(vector<string>& A) {

int ans = 0;

for (int c = 0; c < A[0].size(); ++c)

for (int r = 1; r < A.size(); ++r) {

if (A[r][c] < A[r - 1][c]) {

++ans;

break;

}

return ans;

}

};

花花酱 LeetCode 942. DI String Match

By zxi on November 18, 2018

Problem

Given a string S that only contains “I” (increase) or “D” (decrease), let N = S.length.

Return any permutation A of [0, 1, ..., N] such that for all i = 0, ..., N-1:

If S[i] == "I", then A[i] < A[i+1]
If S[i] == "D", then A[i] > A[i+1]

Example 1:

Input: "IDID"
Output: [0,4,1,3,2]

Example 2:

Input: "III"
Output: [0,1,2,3]

Example 3:

Input: "DDI"
Output: [3,2,0,1]

Note:

1 <= S.length <= 10000
S only contains characters "I" or "D".

Solution: Greedy

“I” -> use the smallest possible number

“D” -> use the largest possible number

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 44 ms

class Solution {

public:

vector<int> diStringMatch(string S) {

const int n = S.length();

vector<int> ans;

int lo = 0;

int hi = n;

for (char c : S) {

if (c == 'I')

ans.push_back(lo++);

else

ans.push_back(hi--);

}

ans.push_back(lo);

return ans;

}

};

花花酱 LeetCode 941. Valid Mountain Array

By zxi on November 18, 2018

Problem

Given an array A of integers, return true if and only if it is a valid mountain array.

Recall that A is a mountain array if and only if:

A.length >= 3
There exists some i with 0 < i < A.length - 1 such that:
- A[0] < A[1] < ... A[i-1] < A[i]
- A[i] > A[i+1] > ... > A[B.length - 1]

Example 1:

Input: [2,1]
Output: false

Example 2:

Input: [3,5,5]
Output: false

Example 3:

Input: [0,3,2,1]
Output: true

Note:

0 <= A.length <= 10000
0 <= A[i] <= 10000

Solution

Use has_up and has_down to track whether we have A[i] > A[i – 1] and A[i] < A[i – 1] receptively.

return false if any of the following happened:

size(A) < 3
has_down happened before has_up
not has_down or not has_up
A[i – 1] < A[i] after has_down
A[i – 1] > A[i] before has_up

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 24 ms

class Solution {

public:

bool validMountainArray(vector<int>& A) {

if (A.size() < 3) return false;

bool has_up = false;

bool has_down = false;

for (int i = 1; i < A.size(); ++i) {

if (A[i] > A[i - 1]) {

if (has_down) return false;

has_up = true;

}

else if (A[i] < A[i - 1]){

if (!has_up) return false;

has_down = true;

} else {

return false;

}

return has_up && has_down;

}

};

花花酱 LeetCode 55. Jump Game

By zxi on November 15, 2018

Problem

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.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

Solution: Greedy

If you can jump to i, then you can jump to at least i + nums[i].

Always jump as far as you can.

Keep tracking the farthest index you can jump to.

Init far = nums[0].

far = max(far, i + nums[i])

check far >= n – 1

ex 1 [2,3,1,1,4]

i nums[i] i + nums[i] far

- - - 2

0 2 2 2

1 3 4 4

2 1 3 4

3 1 4 4

4 4 8 8

ex 2 [3,2,1,0,4]

i nums[i] i + nums[i] far

- - - 3

0 3 3 3

1 2 3 3

2 1 3 3

3 0 3 3 <- can not reach index 4, break

C++

// Author: Huahua, running time 16 ms

class Solution {

public:

bool canJump(vector<int>& nums) {

const int n = nums.size();

int far = nums[0];

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

if (i > far) break;

far = max(far, i + nums[i]);

}

return far >= n-1;

}

};

Huahua's Tech Road

花花酱 LeetCode 943. Find the Shortest Superstring

Problem

Solution 1: Search + Pruning

C++

Java

Solution 2: DP

C++

花花酱 LeetCode 944. Delete Columns to Make Sorted

Problem

Solution: Simulation

C++

花花酱 LeetCode 942. DI String Match

Problem

Solution: Greedy

C++

花花酱 LeetCode 941. Valid Mountain Array

Problem

Solution

C++

花花酱 LeetCode 55. Jump Game

Problem

Solution: Greedy

C++