Posts published in “Search”

花花酱 LeetCode 1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows

By zxi on May 5, 2020

You are given an m * n matrix, mat, and an integer k, which has its rows sorted in non-decreasing order.

You are allowed to choose exactly 1 element from each row to form an array. Return the Kth smallest array sum among all possible arrays.

Example 1:

Input: mat = [[1,3,11],[2,4,6]], k = 5
Output: 7
Explanation: Choosing one element from each row, the first k smallest sum are:
[1,2], [1,4], [3,2], [3,4], [1,6]. Where the 5th sum is 7.

Example 2:

Input: mat = [[1,3,11],[2,4,6]], k = 9
Output: 17

Example 3:

Input: mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
Output: 9
Explanation: Choosing one element from each row, the first k smallest sum are:
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]. Where the 7th sum is 9.

Example 4:

Input: mat = [[1,1,10],[2,2,9]], k = 7
Output: 12

Constraints:

m == mat.length
n == mat.length[i]
1 <= m, n <= 40
1 <= k <= min(200, n ^ m)
1 <= mat[i][j] <= 5000
mat[i] is a non decreasing array.

Solution 1: Priority Queue

Generate the arrays in order.

Each node is {sum, idx_0, idx_1, …, idx_m},

Start with {sum_0, 0, 0, …, 0}.

For expansion, pick one row and increase its index

Time complexity: O(k * m ^ 2* log k)
Space complexity: O(k)

C++

// Author: Huahua

class Solution {

public:

int kthSmallest(vector<vector<int>>& mat, int k) {

const int m = mat.size();

const int n = mat[0].size();

priority_queue<vector<int>> q;

vector<int> node(m + 1); // {-sum, idx_0, idx_1, ..., idx_m}

for (int i = 0; i < m; ++i) node[0] -= mat[i][0];

q.push(node);

set<vector<int>> seen{{node}};

while (!q.empty()) {

const vector<int> cur = q.top(); q.pop();

if (--k == 0) return -cur[0];

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

if (cur[i] == n - 1) continue;

vector<int> nxt(cur);

++nxt[i]; // increase i-th row's index.

// Update sum.

nxt[0] -= (mat[i - 1][nxt[i]] - mat[i - 1][nxt[i] - 1]);

if (!seen.insert(nxt).second) continue;

q.push(move(nxt));

}

return -1;

}

};

花花酱 LeetCode 1415. The k-th Lexicographical String of All Happy Strings of Length n

By zxi on April 18, 2020

A happy string is a string that:

consists only of letters of the set ['a', 'b', 'c'].
s[i] != s[i + 1] for all values of i from 1 to s.length - 1 (string is 1-indexed).

For example, strings “abc”, “ac”, “b” and “abcbabcbcb” are all happy strings and strings “aa”, “baa” and “ababbc” are not happy strings.

Given two integers n and k, consider a list of all happy strings of length n sorted in lexicographical order.

Return the kth string of this list or return an empty string if there are less than k happy strings of length n.

Example 1:

Input: n = 1, k = 3
Output: "c"
Explanation: The list ["a", "b", "c"] contains all happy strings of length 1. The third string is "c".

Example 2:

Input: n = 1, k = 4
Output: ""
Explanation: There are only 3 happy strings of length 1.

Example 3:

Input: n = 3, k = 9
Output: "cab"
Explanation: There are 12 different happy string of length 3 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"]. You will find the 9th string = "cab"

Example 4:

Input: n = 2, k = 7
Output: ""

Example 5:

Input: n = 10, k = 100
Output: "abacbabacb"

Constraints:

1 <= n <= 10
1 <= k <= 100

Solution: DFS

Generate the happy strings in lexical order, store the k-th one.
Time complexity: O(n + k)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

string getHappyString(int n, int k) {

string ans;

string cur;

function<void()> dfs = [&]() {

if (k <= 0) return;

if (cur.length() == n) {

if (--k == 0) ans = cur;

return;

}

for (char ch = 'a'; ch <= 'c'; ++ch) {

if (!cur.empty() && ch == cur.back()) continue;

cur.push_back(ch);

dfs();

cur.pop_back();

}

};

dfs();

return k > 0 ? "" : ans;

}

};

花花酱 LeetCode 1391. Check if There is a Valid Path in a Grid

By zxi on March 22, 2020

Given a m x ngrid. Each cell of the grid represents a street. The street of grid[i][j] can be:

1 which means a street connecting the left cell and the right cell.
2 which means a street connecting the upper cell and the lower cell.
3 which means a street connecting the left cell and the lower cell.
4 which means a street connecting the right cell and the lower cell.
5 which means a street connecting the left cell and the upper cell.
6 which means a street connecting the right cell and the upper cell.

You will initially start at the street of the upper-left cell (0,0). A valid path in the grid is a path which starts from the upper left cell (0,0) and ends at the bottom-right cell (m - 1, n - 1). The path should only follow the streets.

Notice that you are not allowed to change any street.

Return true if there is a valid path in the grid or false otherwise.

Example 1:

Input: grid = [[2,4,3],[6,5,2]]
Output: true
Explanation: As shown you can start at cell (0, 0) and visit all the cells of the grid to reach (m - 1, n - 1).

Example 2:

Input: grid = [[1,2,1],[1,2,1]]
Output: false
Explanation: As shown you the street at cell (0, 0) is not connected with any street of any other cell and you will get stuck at cell (0, 0)

Example 3:

Input: grid = [[1,1,2]]
Output: false
Explanation: You will get stuck at cell (0, 1) and you cannot reach cell (0, 2).

Example 4:

Input: grid = [[1,1,1,1,1,1,3]]
Output: true

Example 5:

Input: grid = [[2],[2],[2],[2],[2],[2],[6]]
Output: true

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
1 <= grid[i][j] <= 6

Solution: BFS

Need to check both sides (x, y) -> (tx, ty) and (tx, ty) -> (x, y) to make sure a path exist.

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

C++

// Author: Huahua

class Solution {

public:

bool hasValidPath(vector<vector<int>>& grid) {

const int m = grid.size();

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

vector<int> dirs{0, -1, 0, 1, 0}; // [up, left, down, right]

vector<set<int>> rules{

{1, 3}, {0, 2}, {1, 2},

{2, 3}, {0, 1}, {0, 3}};

queue<int> q{{0}};

vector<int> seen(m * n);

seen[0] = 1;

while (!q.empty()) {

int cx = q.front() % n;

int cy = q.front() / n;

q.pop();

if (cx == n - 1 && cy == m - 1) return true;

for (int d : rules[grid[cy][cx] - 1]) {

int x = cx + dirs[d];

int y = cy + dirs[d + 1];

int key = y * n + x;

if (x < 0 || x >= n || y < 0 || y >= m || seen[key]

|| !rules[grid[y][x] - 1].count((d + 2) % 4)) continue;

seen[key] = 1;

q.push(key);

}

return false;

}

};

花花酱 LeetCode 87. Scramble String

By zxi on March 14, 2020

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Example 1:

Input: s1 = "great", s2 = "rgeat"
Output: true

Example 2:

Input: s1 = "abcde", s2 = "caebd"
Output: false

Solution: Recursion

isScramble(s1, s2)
if s1 == s2: return true
if sorted(s1) != sroted(s2): return false
We try all possible partitions:

s1[0:l] v.s s2[0:l] && s1[l:] vs s2[l:]
s1[0:l] vs s2[L-l:l] && s1[l:] vs s2[0:L-l]

Time complexity: O(n^5)
Space complexity: O(n^4)

C++

class Solution {

public:

bool isScramble(string_view s1, string_view s2) {

const int l = s1.length();

if (s1 == s2) return true;

if (freq(s1) != freq(s2)) return false;

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

if (isScramble(s1.substr(0, i), s2.substr(0, i))

&& isScramble(s1.substr(i), s2.substr(i))

|| isScramble(s1.substr(0, i), s2.substr(l - i, i))

&& isScramble(s1.substr(i), s2.substr(0, l - i)))

return true;

return false;

}

private:

vector<int> freq(string_view s) {

vector<int> f(26);

for (char c : s) ++f[c - 'a'];

return f;

}

};

Python3

# Author: Huahua

class Solution:

@lru_cache(maxsize=None) # optional

def isScramble(self, s1: str, s2: str) -> bool:

if s1 == s2: return True

# important, TLE if commneted out

if Counter(s1) != Counter(s2): return False

L = len(s1)

for l in range(1, L):

if self.isScramble(s1[0:l], s2[0:l]) and self.isScramble(s1[l:], s2[l:]):

return True

if self.isScramble(s1[0:l], s2[L-l:]) and self.isScramble(s1[l:], s2[0:L-l]):

return True

return False

花花酱 LeetCode 306. Additive Number

By zxi on March 14, 2020

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

Given a string containing only digits '0'-'9', write a function to determine if it’s an additive number.

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Example 1:

Input: "112358"
Output: true
Explanation: The digits can form an additive sequence: 1, 1, 2, 3, 5, 8. 
             1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

Example 2:

Input: "199100199"
Output: true
Explanation: The additive sequence is: 1, 99, 100, 199. 
             1 + 99 = 100, 99 + 100 = 199

Constraints:

num consists only of digits '0'-'9'.
1 <= num.length <= 35

Solution: DFS

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

C++

using SV = std::string_view;

class Solution {

public:

bool isAdditiveNumber(SV s) {

auto add = [](SV s1, SV s2) {

const int l1 = s1.length(), l2 = s2.length();

string s3(max(l1, l2) + 1, '0');

for (int i = 0; i < s3.size() - 1; ++i) {

int n1 = i < l1 ? s1[l1 - i - 1] - '0' : 0;

int n2 = i < l2 ? s2[l2 - i - 1] - '0' : 0;

s3[i] += n1 + n2;

if (s3[i] > '9') {

s3[i] -= 10;

++s3[i + 1];

}

while (s3.back() == '0' && s3.length() > 1) s3.pop_back();

return string{rbegin(s3), rend(s3)};

};

auto isValid = [](SV s) { return s.length() == 1 || s[0] != '0'; };

function<bool(SV, SV, SV)> additive = [&](SV s1, SV s2, SV right) {

if (!isValid(s1) || !isValid(s2)) return false;

string s3 = add(s1, s2);

const int l3 = s3.length();

if (right.substr(0, l3) != s3) return false;

if (right.length() == l3) return true;

return additive(s2, s3, right.substr(l3));

};

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

for (int j = 1; i + j <= s.size(); ++j)

if (additive(s.substr(0, i), s.substr(i, j), s.substr(i + j)))

return true;

return false;

}

};

Python3

class Solution:

def isAdditiveNumber(self, num: str) -> bool:

n = len(num)

def valid(s): return len(s) == 1 or s[0] != '0'

def additive(s1, s2, right):

if not valid(s1) or not valid(s2): return False

s3 = str(int(s1) + int(s2))

if right.startswith(s3):

if right == s3: return True

return additive(s2, s3, right[len(s3):])

return False

for l1 in range(1, n // 2 + 1):

for l2 in range(1, n + 1 - l1):

if additive(num[:l1], num[l1:l1+l2], num[l1+l2:]):

return True

return False