Posts published in “Search”

花花酱 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 909. Snakes and Ladders

By zxi on September 25, 2018

Problem

On an N x N board, the numbers from 1 to N*N are written boustrophedonically starting from the bottom left of the board, and alternating direction each row. For example, for a 6 x 6 board, the numbers are written as follows:

You start on square 1 of the board (which is always in the last row and first column). Each move, starting from square x, consists of the following:

You choose a destination square S with number x+1, x+2, x+3, x+4, x+5, or x+6, provided this number is <= N*N.
- (This choice simulates the result of a standard 6-sided die roll: ie., there are always at most 6 destinations.)
If S has a snake or ladder, you move to the destination of that snake or ladder. Otherwise, you move to S.

A board square on row r and column c has a “snake or ladder” if board[r][c] != -1. The destination of that snake or ladder is board[r][c].

Note that you only take a snake or ladder at most once per move: if the destination to a snake or ladder is the start of another snake or ladder, you do not continue moving. (For example, if the board is [[4,-1],[-1,3]], and on the first move your destination square is 2, then you finish your first move at 3, because you do notcontinue moving to 4.)

Return the least number of moves required to reach square N*N. If it is not possible, return -1.

Example 1:

Input: [
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,35,-1,-1,13,-1],
[-1,-1,-1,-1,-1,-1],
[-1,15,-1,-1,-1,-1]]
Output: 4
Explanation: 
At the beginning, you start at square 1 [at row 5, column 0].
You decide to move to square 2, and must take the ladder to square 15.
You then decide to move to square 17 (row 3, column 5), and must take the snake to square 13.
You then decide to move to square 14, and must take the ladder to square 35.
You then decide to move to square 36, ending the game.
It can be shown that you need at least 4 moves to reach the N*N-th square, so the answer is 4.

Note:

2 <= board.length = board[0].length <= 20
board[i][j] is between 1 and N*N or is equal to -1.
The board square with number 1 has no snake or ladder.
The board square with number N*N has no snake or ladder.

Solution: BFS

Time complexity: O(n*n)

Space complexity: O(n*n)

C++

// Author: Huahua, 8 ms (beats 100%)

class Solution {

public:

int snakesAndLadders(vector<vector<int>>& board) {

const int N = board.size();

int steps = 0;

vector<int> seen(N * N + 1, 0);

queue<int> q;

q.push(1);

seen[1] = 1;

while (!q.empty()) {

int size = q.size();

++steps;

while (size--) {

int s = q.front(); q.pop();

for (int x = s + 1; x <= min(s + 6, N * N); ++x) {

int r, c;

getRC(x, N, &r, &c);

int nx = board[r][c] == -1 ? x : board[r][c];

if (seen[nx]) continue;

if (nx == N * N) return steps;

q.push(nx);

seen[nx] = 1;

}

return -1;

}

private:

void getRC(int s, int N, int* r, int* c) {

int y = (s - 1) / N;

int x = (s - 1) % N;

*r = N - 1 - y;

*c = (y % 2) ? N - 1 - x : x;

}

};

花花酱 LeetCode 10. Regular Expression Matching

By zxi on September 17, 2018

Problem

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".

Example 5:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

Solution 1: Recursion

Time complexity: O((|s| + |p|) * 2 ^ (|s| + |p|))

Space complexity: O(|s| + |p|)

C++

// Author: Huahua, 14 ms

class Solution {

public:

bool isMatch(string s, string p) {

return isMatch(s.c_str(), p.c_str());

}

private:

bool isMatch(const char* s, const char* p) {

if (*p == '\0') return *s == '\0';

// normal case, e.g. 'a.b','aaa', 'a'

if (p[1] != '*' || p[1] == '\0') {

// no char to match

if (*s == '\0') return false;

if (*s == *p || *p == '.')

return isMatch(s + 1, p + 1);

else

return false;

}

else {

int i = -1;

while (i == -1 || s[i] == p[0] || p[0] == '.') {

if (isMatch(s + i + 1, p + 2)) return true;

if (s[++i] == '\0') break;

}

return false;

}

return false;

}

};

花花酱 LeetCode 638. Shopping Offers

By zxi on August 6, 2018

Problem

In LeetCode Store, there are some kinds of items to sell. Each item has a price.

However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.

You are given the each item’s price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers.

Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer.

You could use any of special offers as many times as you want.

Example 1:

Input: [2,5], [[3,0,5],[1,2,10]], [3,2]
Output: 14
Explanation: 
There are two kinds of items, A and B. Their prices are $2 and $5 respectively. 
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B. 
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.

Example 2:

Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
Output: 11
Explanation: 
The price of A is $2, and $3 for B, $4 for C. 
You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C. 
You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C. 
You cannot add more items, though only $9 for 2A ,2B and 1C.

Note:

There are at most 6 kinds of items, 100 special offers.
For each item, you need to buy at most 6 of them.
You are not allowed to buy more items than you want, even if that would lower the overall price.

Solution: Search

Try all combinations.

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {

int with_offer = INT_MAX;

for (const auto& offer : special) {

vector<int> new_needs(needs);

bool valid_offer = true;

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

if (!(valid_offer &= ((new_needs[i] -= offer[i]) >= 0)))

break;

if (!valid_offer) continue;

with_offer = min(with_offer, shoppingOffers(price, special, new_needs) + offer.back());

}

int without_offer = inner_product(begin(price), end(price), begin(needs), 0);

return min(with_offer, without_offer);

}

};

花花酱 LeetCode 842. Split Array into Fibonacci Sequence

By zxi on July 26, 2018

Problem

Given a string S of digits, such as S = "123456579", we can split it into a Fibonacci-like sequence [123, 456, 579].

Formally, a Fibonacci-like sequence is a list F of non-negative integers such that:

0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type);
F.length >= 3;
and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2.

Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself.

Return any Fibonacci-like sequence split from S, or return [] if it cannot be done.

Example 1:

Input: "123456579"
Output: [123,456,579]

Example 2:

Input: "11235813"
Output: [1,1,2,3,5,8,13]

Example 3:

Input: "112358130"
Output: []
Explanation: The task is impossible.

Example 4:

Input: "0123"
Output: []
Explanation: Leading zeroes are not allowed, so "01", "2", "3" is not valid.

Example 5:

Input: "1101111"
Output: [110, 1, 111]
Explanation: The output [11, 0, 11, 11] would also be accepted.

Note:

1 <= S.length <= 200
S contains only digits.

Solution: DFS

Time complexity: O(2^n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

vector<int> splitIntoFibonacci(string s) {

const int n = s.length();

vector<int> nums;

function<bool(int)> dfs = [&](int pos) {

if (pos == n) return nums.size() >= 3;

int max_len = s[pos] == '0' ? 1 : 10;

long num = 0;

for (int i = pos; i < min(pos + max_len, n); ++i) {

num = num * 10 + (s[i] - '0');

if (num > INT_MAX) break;

if (nums.size() >= 2) {

long sum = nums.rbegin()[0];

sum += nums.rbegin()[1];

if (num > sum) break;

else if (num < sum) continue;

// num must equaals to sum.

}

nums.push_back(num);

if (dfs(i + 1)) return true;

nums.pop_back();

}

return false;

};

dfs(0);

return nums;

}

};