Posts tagged as “hard”

花花酱 LeetCode 132. Palindrome Partitioning II

By zxi on December 7, 2019

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example:

Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Solution: DP

dp[i] := min cuts of s[0~i]
dp[i] = min{dp[j] + 1} if s[j+1~i] is a palindrome.

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

C++

// Author: Huahua

class Solution {

public:

int minCut(string s) {

const int n = s.length();

// valid[i][j] = 1 if s[i~j] is palindrome, otherwise 0

vector<vector<int>> valid(n, vector<int>(n, 1));

// dp[i] = min cuts of s[0~i]

vector<int> dp(n, n);

for (int l = 2; l <= n; ++l)

for (int i = 0, j = i + l - 1; j < n; ++i, ++j)

valid[i][j] = s[i] == s[j] && valid[i + 1][j - 1];

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

if (valid[0][i]) {

dp[i] = 0;

continue;

}

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

if (valid[j + 1][i])

dp[i] = min(dp[i], dp[j] + 1);

}

return dp[n - 1];

}

};

DP v2

C++

// Author: Huahua

class Solution {

public:

int minCut(string s) {

const int n = s.length();

// dp[i] = min cuts of s[0~i]

vector<int> dp(n, n);

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

for (int d = 0; d <= 1; ++d)

for (int i = m, j = m + d; i >= 0 && j < n && s[i] == s[j]; --i, ++j)

dp[j] = min(dp[j], (i ? (dp[i - 1] + 1) : 0));

return dp[n - 1];

}

};

花花酱 LeetCode 1278. Palindrome Partitioning III

By zxi on December 2, 2019

You are given a string s containing lowercase letters and an integer k. You need to :

First, change some characters of s to other lowercase English letters.
Then divide s into k non-empty disjoint substrings such that each substring is palindrome.

Return the minimal number of characters that you need to change to divide the string.

Example 1:

Input: s = "abc", k = 2
Output: 1
Explanation: You can split the string into "ab" and "c", and change 1 character in "ab" to make it palindrome.

Example 2:

Input: s = "aabbc", k = 3
Output: 0
Explanation: You can split the string into "aa", "bb" and "c", all of them are palindrome.

Example 3:

Input: s = "leetcode", k = 8
Output: 0

Constraints:

1 <= k <= s.length <= 100.
s only contains lowercase English letters.

Solution: DP

dp[i][k] := min changes to make s[0~i] into k palindromes
dp[i][k] = min(dp[j][k – 1] + cost(j + 1, i)) 0 <= j < i

ans = dp[n-1][K]

Time complexity: O(n^2 * K) = O(n^3)
Space complexity: O(n*n + n*K) = O(n^2)

C++

// Author: Huahua, 8 ms, 9.1 MB

class Solution {

public:

int palindromePartition(string s, int K) {

const int n = s.length();

auto minChange = [&](int i, int j) {

int c = 0;

while (i < j)

if (s[i++] != s[j--]) ++c;

return c;

};

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

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

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

cost[i][j] = minChange(i, j);

// dp[i][j] := min changes to make s[0~i] into k palindromes

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

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

dp[i][1] = cost[0][i];

for (int k = 1; k <= K; ++k)

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

dp[i][k] = min(dp[i][k], dp[j][k - 1] + cost[j + 1][i]);

}

return dp[n - 1][K];

}

};

C++/DP+DP

// Author: Huahua, 4 ms, 9.1MB

class Solution {

public:

int palindromePartition(string s, int K) {

const int n = s.length();

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

for (int l = 2; l <= n; ++l)

for (int i = 0, j = l - 1; j < n; ++i, ++j)

cost[i][j] = (s[i] != s[j]) + cost[i + 1][j - 1];

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

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

dp[i][1] = cost[0][i];

for (int k = 2; k <= K; ++k)

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

dp[i][k] = min(dp[i][k], dp[j][k - 1] + cost[j + 1][i]);

}

return dp[n - 1][K];

}

};

Python3

// Author: Huahua

import functools

class Solution:

def palindromePartition(self, s: str, K: int) -> int:

@functools.lru_cache(None)

def cost(i: int, j: int) -> int:

if i >= j: return 0

return cost(i + 1, j - 1) + (1 if s[i] != s[j] else 0)

@functools.lru_cache(None)

def dp(i: int, k: int) -> int:

if k == 1: return cost(0, i)

if k == i + 1: return 0

if k > i + 1: return 1**9

return min([dp(j, k - 1) + cost(j + 1, i) for j in range(i)])

return dp(len(s) - 1, K)

花花酱 LeetCode 1274. Number of Ships in a Rectangle

By zxi on December 1, 2019

(This problem is an interactive problem.)

On the sea represented by a cartesian plane, each ship is located at an integer point, and each integer point may contain at most 1 ship.

You have a function Sea.hasShips(topRight, bottomLeft) which takes two points as arguments and returns true if and only if there is at least one ship in the rectangle represented by the two points, including on the boundary.

Given two points, which are the top right and bottom left corners of a rectangle, return the number of ships present in that rectangle. It is guaranteed that there are at most 10 ships in that rectangle.

Submissions making more than 400 calls to hasShips will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

Example :

Input: 
ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
Output: 3
Explanation: From [0,0] to [4,4] we can count 3 ships within the range.

Constraints:

On the input ships is only given to initialize the map internally. You must solve this problem “blindfolded”. In other words, you must find the answer using the given hasShips API, without knowing the ships position.
0 <= bottomLeft[0] <= topRight[0] <= 1000
0 <= bottomLeft[1] <= topRight[1] <= 1000

Solution: Divide and Conquer

If the current rectangle contains ships, subdivide it into 4 smaller ones until
1) no ships contained
2) the current rectangle is a single point (e.g. topRight == bottomRight)

Time complexity: O(logn)
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

// Modify the interface to pass sea as a reference.

int countShips(Sea& sea, vector<int> topRight, vector<int> bottomLeft) {

int x1 = bottomLeft[0], y1 = bottomLeft[1];

int x2 = topRight[0], y2 = topRight[1];

if (x1 > x2 || y1 > y2 || !sea.hasShips(topRight, bottomLeft))

return 0;

if (x1 == x2 && y1 == y2)

return 1;

int xm = x1 + (x2 - x1) / 2;

int ym = y1 + (y2 - y1) / 2;

return countShips(sea, {xm, ym}, {x1, y1}) + countShips(sea, {xm, y2}, {x1, ym + 1})

+ countShips(sea, {x2, ym}, {xm + 1, y1}) + countShips(sea, {x2, y2}, {xm + 1, ym + 1});

}

};

花花酱 LeetCode 1263. Minimum Moves to Move a Box to Their Target Location

By zxi on November 26, 2019

Storekeeper is a game in which the player pushes boxes around in a warehouse trying to get them to target locations.

The game is represented by a grid of size n*m, where each element is a wall, floor, or a box.

Your task is move the box 'B' to the target position 'T' under the following rules:

Player is represented by character 'S' and can move up, down, left, right in the grid if it is a floor (empy cell).
Floor is represented by character '.' that means free cell to walk.
Wall is represented by character '#' that means obstacle (impossible to walk there).
There is only one box 'B' and one target cell 'T' in the grid.
The box can be moved to an adjacent free cell by standing next to the box and then moving in the direction of the box. This is a push.
The player cannot walk through the box.

Return the minimum number of pushes to move the box to the target. If there is no way to reach the target, return -1.

Example 1:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#",".","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 3
Explanation: We return only the number of times the box is pushed.

Example 2:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#","#","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: -1

Example 3:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T",".",".","#","#"],
               ["#",".","#","B",".","#"],
               ["#",".",".",".",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 5
Explanation:  push the box down, left, left, up and up.

Example 4:

Input: grid = [["#","#","#","#","#","#","#"],
               ["#","S","#",".","B","T","#"],
               ["#","#","#","#","#","#","#"]]
Output: -1

Constraints:

1 <= grid.length <= 20
1 <= grid[i].length <= 20
grid contains only characters '.', '#', 'S' , 'T', or 'B'.
There is only one character 'S', 'B' and 'T' in the grid.

Solution: BFS + DFS

BFS to search by push steps to find miminal number of pushes. Each time we move from the previous position (initial position or last push position) to a new push position. Use DFS to check that whether that path exist or not.

C++

// Author: Huahua

struct Node {

int bx;

int by;

int px;

int py;

int key() const { return ((by * 20 + bx) << 16) | (py * 20 + px); }

};

class Solution {

public:

int minPushBox(vector<vector<char>>& grid) {

const int n = grid.size();

const int m = grid[0].size();

Node start;

Node end;

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

for (int x = 0; x < m; ++x)

if (grid[y][x] == 'B') {

start.bx = x;

start.by = y;

} else if (grid[y][x] == 'S') {

start.px = x;

start.py = y;

} else if (grid[y][x] == 'T') {

end.bx = x;

end.by = y;

}

auto hasPath = [&](const Node& cur, int tx, int ty) {

vector<int> seen(m*n);

function<bool(int, int)> dfs = [&](int x, int y) {

if (x < 0 || x >= m || y < 0 || y >= n || grid[y][x] == '#')

return false;

if (x == cur.bx && y == cur.by) return false;

int key = y * m + x;

if (seen[key]) return false;

seen[key] = 1;

if (x == tx && y == ty) return true;

return dfs(x + 1, y) || dfs(x - 1, y) || dfs(x, y + 1) || dfs(x, y - 1);

};

return dfs(cur.px, cur.py);

};

auto canPush = [&](const Node& cur, int dx, int dy, Node* nxt) {

const int bx = cur.bx + dx;

const int by = cur.by + dy;

if (bx < 0 || bx >= m || by < 0 || by >= n || grid[by][bx] == '#')

return false;

if (!hasPath(cur, cur.bx - dx, cur.by - dy)) return false;

nxt->bx = bx;

nxt->by = by;

nxt->px = cur.bx;

nxt->py = cur.by;

return true;

};

const vector<int> dirs{0, -1, 0, 1, 0};

unordered_set<int> seen;

queue<Node> q;

q.push(start);

int steps = 0;

while (q.size()) {

int size = q.size();

while (size--) {

Node cur = q.front();

q.pop();

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

Node nxt;

if (!canPush(cur, dirs[i], dirs[i + 1], &nxt) ||

seen.count(nxt.key()))

continue;

if (nxt.bx == end.bx && nxt.by == end.by) return steps + 1;

seen.insert(nxt.key());

q.push(nxt);

}

++steps;

}

return -1;

}

};

**Solution: A* + BFS**

g : history = # of pushes
h: heuristics = Manhattan distance from the current box position to the target position, always <= actual moves.
f = g + h

C++

100

101

// Author: Huahua, 4 ms, 17.5 MB

struct Node {

int bx;

int by;

int px;

int py;

int h;

int g;

int key() const {

return ((by * m + bx) << 2) | ((bx - px) + 1) | ((by - py) + 1) >> 1;

}

int f() const { return g + h; }

bool operator< (const Node& o) const {

return f() > o.f();

}

static int m;

};

int Node::m;

class Solution {

public:

int minPushBox(vector<vector<char>>& grid) {

const vector<int> dirs{0, -1, 0, 1, 0};

const int n = grid.size();

const int m = Node::m = grid[0].size();

Node start;

Node end;

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

for (int x = 0; x < m; ++x)

if (grid[y][x] == 'B') {

start.bx = x;

start.by = y;

} else if (grid[y][x] == 'S') {

start.px = x;

start.py = y;

} else if (grid[y][x] == 'T') {

end.bx = x;

end.by = y;

}

auto isValid = [&](int x, int y) {

return !(x < 0 || x >= m || y < 0 || y >= n || grid[y][x] == '#');

};

auto hasPath = [&](const Node& cur, int tx, int ty) {

if (!isValid(tx, ty)) return false;

vector<int> seen(m*n);

queue<int> q;

q.push(cur.py * m + cur.px);

seen[cur.py * m + cur.px] = 1;

while (q.size()) {

int x = q.front() % m;

int y = q.front() / m;

q.pop();

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

int nx = x + dirs[i];

int ny = y + dirs[i + 1];

if (!isValid(nx, ny)) continue;

if (nx == cur.bx && ny == cur.by) continue;

if (nx == tx && ny == ty) return true;

if (seen[ny * m + nx]++) continue;

q.push(ny * m + nx);

}

return false;

};

auto canPush = [&](const Node& cur, int dx, int dy, Node* nxt) {

nxt->bx = cur.bx + dx;

nxt->by = cur.by + dy;

nxt->px = cur.bx;

nxt->py = cur.by;

nxt->g = cur.g + 1;

nxt->h = abs(nxt->bx - end.bx) + abs(nxt->by - end.by);

if (!isValid(nxt->bx, nxt->by)) return false;

return hasPath(cur, cur.bx - dx, cur.by - dy);

};

vector<int> seen(m*n*4);

priority_queue<Node> q;

start.g = 0;

start.h = abs(start.bx - end.bx) + abs(start.by - end.by);

q.push(start);

while (q.size()) {

Node cur = q.top();

q.pop();

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

Node nxt;

if (!canPush(cur, dirs[i], dirs[i + 1], &nxt) || seen[nxt.key()]++) continue;

if (nxt.bx == end.bx && nxt.by == end.by) return nxt.g;

q.push(nxt);

}

return -1;

}

};

花花酱 LeetCode 1269. Number of Ways to Stay in the Same Place After Some Steps

By zxi on November 24, 2019

You have a pointer at index 0 in an array of size arrLen. At each step, you can move 1 position to the left, 1 position to the right in the array or stay in the same place (The pointer should not be placed outside the array at any time).

Given two integers steps and arrLen, return the number of ways such that your pointer still at index 0 after exactly steps steps.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: steps = 3, arrLen = 2
Output: 4
Explanation: There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, Stay

Example 2:

Input: steps = 2, arrLen = 4
Output: 2
Explanation: There are 2 differents ways to stay at index 0 after 2 steps
Right, Left
Stay, Stay

Example 3:

Input: steps = 4, arrLen = 2
Output: 8

Constraints:

1 <= steps <= 500
1 <= arrLen <= 10^6

Solution: DP

Since we can move at most steps, we can reduce the arrLen to min(arrLen, steps + 1).

dp[i][j] = dp[i-1][j – 1] + dp[i-1][j] + dp[i-1][j+1] // sum of right, stay, left

Time complexity: O(steps * steps)
Space complexity: O(steps)

C++

// Author: Huahua

class Solution {

public:

int numWays(int steps, int arrLen) {

const int kMod = 1e9 + 7;

arrLen = min(steps + 1, arrLen);

vector<int> dp(arrLen);

dp[0] = 1;

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

vector<int> tmp(dp.size());

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

tmp[j] = dp[j];

if (j > 0) tmp[j] = (tmp[j] + dp[j - 1]) % kMod;

if (j < arrLen - 1) tmp[j] = (tmp[j] + dp[j + 1]) % kMod;

}

swap(dp, tmp);

}

return dp[0];

}

};

Posts tagged as “hard”

花花酱 LeetCode 132. Palindrome Partitioning II

Solution: DP

C++

C++

Related Problems

花花酱 LeetCode 1278. Palindrome Partitioning III

Solution: DP

C++

C++/DP+DP

Python3

花花酱 LeetCode 1274. Number of Ships in a Rectangle

Solution: Divide and Conquer

C++

花花酱 LeetCode 1263. Minimum Moves to Move a Box to Their Target Location

Solution: BFS + DFS

C++

Solution: A* + BFS

C++

花花酱 LeetCode 1269. Number of Ways to Stay in the Same Place After Some Steps

Solution: DP

C++

**Solution: A* + BFS**