Huahua’s Tech Road

花花酱 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];

}

};

花花酱 LeetCode 1268. Search Suggestions System

By zxi on November 24, 2019

Given an array of strings products and a string searchWord. We want to design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with the searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return list of lists of the suggested products after each character of searchWord is typed.

Example 1:

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"]
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"]
After typing mou, mous and mouse the system suggests ["mouse","mousepad"]

Example 2:

Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

Example 3:

Input: products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
Output: [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

Example 4:

Input: products = ["havana"], searchWord = "tatiana"
Output: [[],[],[],[],[],[],[]]

Constraints:

1 <= products.length <= 1000
1 <= Σ products[i].length <= 2 * 10^4
All characters of products[i] are lower-case English letters.
1 <= searchWord.length <= 1000
All characters of searchWord are lower-case English letters.

Solution 1: Binary Search

Sort the input array and do two binary searches.
One for prefix of the search word as lower bound, another for prefix + ‘~’ as upper bound.
‘~’ > ‘z’

Time complexity: O(nlogn + l * logn)
Space complexity: O(1)

C++

// Author: Huahua, 36ms, 35MB

class Solution {

public:

vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {

vector<vector<string>> ans;

std::sort(begin(products), end(products));

string key;

for (char c : searchWord) {

key += c;

auto l = lower_bound(begin(products), end(products), key);

auto r = upper_bound(begin(products), end(products), key += '~');

if (l == r) break; // early return

key.pop_back();

ans.emplace_back(l, min(l + 3, r));

}

while (ans.size() != searchWord.length()) ans.push_back({});

return ans;

}

};

Solution 2: Trie

Initialization: Sum(len(products[i]))
Query: O(len(searchWord))

C++

// Author: Huahua, 148 ms, 98.8 MB

struct Trie {

Trie(): nodes(26) {}

~Trie() {

for (auto* node : nodes)

delete node;

}

vector<Trie*> nodes;

vector<const string*> words;

static void addWord(Trie* root, const string& word) {

for (char c : word) {

if (root->nodes[c - 'a'] == nullptr) root->nodes[c - 'a'] = new Trie();

root = root->nodes[c - 'a'];

if (root->words.size() < 3)

root->words.push_back(&word);

}

static vector<vector<string>> getWords(Trie* root, const string& prefix) {

vector<vector<string>> ans(prefix.size());

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

char c = prefix[i];

root = root->nodes[c - 'a'];

if (root == nullptr) break;

for (auto* word : root->words)

ans[i].push_back(*word);

}

return ans;

}

};

class Solution {

public:

vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {

std::sort(begin(products), end(products));

Trie root;

for (const auto& product : products)

Trie::addWord(&root, product);

return Trie::getWords(&root, searchWord);

}

};

花花酱 LeetCode 1267. Count Servers that Communicate

By zxi on November 23, 2019

You are given a map of a server center, represented as a m * n integer matrix grid, where 1 means that on that cell there is a server and 0 means that it is no server. Two servers are said to communicate if they are on the same row or on the same column.

Return the number of servers that communicate with any other server.

Example 1:

Input: grid = [[1,0],[0,1]]
Output: 0
Explanation: No servers can communicate with others.

Example 2:

Input: grid = [[1,0],[1,1]]
Output: 3
Explanation: All three servers can communicate with at least one other server.

Example 3:

Input: grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
Output: 4
Explanation: The two servers in the first row can communicate with each other. The two servers in the third column can communicate with each other. The server at right bottom corner can't communicate with any other server.

Constraints:

m == grid.length
n == grid[i].length
1 <= m <= 250
1 <= n <= 250
grid[i][j] == 0 or 1

Solution: Counting

Two passes:
First pass, count number of computers for each row and each column.
Second pass, count grid[i][j] if rows[i] or cols[j] has more than 1 computer.

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

C++

// Author: Huahua

class Solution {

public:

int countServers(vector<vector<int>>& grid) {

const size_t m = grid.size();

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

vector<int> rows(m);

vector<int> cols(n);

for (size_t i = 0; i < m; ++i)

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

rows[i] += grid[i][j];

cols[j] += grid[i][j];

}

int ans = 0;

for (size_t i = 0; i < m; ++i)

for (size_t j = 0; j < n; ++j)

ans += (rows[i] > 1 || cols[j] > 1) ? grid[i][j] : 0;

return ans;

}

};

花花酱 LeetCode 1266. Minimum Time Visiting All Points

By zxi on November 23, 2019

On a plane there are n points with integer coordinates points[i] = [xi, yi]. Your task is to find the minimum time in seconds to visit all points.

You can move according to the next rules:

In one second always you can either move vertically, horizontally by one unit or diagonally (it means to move one unit vertically and one unit horizontally in one second).
You have to visit the points in the same order as they appear in the array.

Example 1:

Input: points = [[1,1],[3,4],[-1,0]]
Output: 7
Explanation: One optimal path is [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]   
Time from [1,1] to [3,4] = 3 seconds 
Time from [3,4] to [-1,0] = 4 seconds
Total time = 7 seconds

Example 2:

Input: points = [[3,2],[-2,2]]
Output: 5

Constraints:

points.length == n
1 <= n <= 100
points[i].length == 2
-1000 <= points[i][0], points[i][1] <= 1000

Solution: Geometry + Greedy

dx = abs(x1 – x2)
dy = abs(y1 – y2)

go diagonally first for min(dx, dy) steps, and then go straight line for abs(dx – dy) steps.

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

C++

// Author: Huahua

class Solution {

public:

int minTimeToVisitAllPoints(vector<vector<int>>& points) {

int ans = 0;

for (size_t i = 1; i < points.size(); ++i) {

int dx = abs(points[i - 1][0] - points[i][0]);

int dy = abs(points[i - 1][1] - points[i][1]);

ans += min(dx, dy) + abs(dx - dy);

}

return ans;

}

};

花花酱 LeetCode 1255. Maximum Score Words Formed by Letters

By zxi on November 9, 2019

Given a list of words, list of single letters (might be repeating) and score of every character.

Return the maximum score of any valid set of words formed by using the given letters (words[i] cannot be used two or more times).

It is not necessary to use all characters in letters and each letter can only be used once. Score of letters 'a', 'b', 'c', … ,'z' is given by score[0], score[1], … , score[25] respectively.

Example 1:

Input: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
Output: 23
Explanation:
Score  a=1, c=9, d=5, g=3, o=2
Given letters, we can form the words "dad" (5+1+5) and "good" (3+2+2+5) with a score of 23.
Words "dad" and "dog" only get a score of 21.

Example 2:

Input: words = ["xxxz","ax","bx","cx"], letters = ["z","a","b","c","x","x","x"], score = [4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10]
Output: 27
Explanation:
Score  a=4, b=4, c=4, x=5, z=10
Given letters, we can form the words "ax" (4+5), "bx" (4+5) and "cx" (4+5) with a score of 27.
Word "xxxz" only get a score of 25.

Example 3:

Input: words = ["leetcode"], letters = ["l","e","t","c","o","d"], score = [0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0]
Output: 0
Explanation:
Letter "e" can only be used once.

Constraints:

1 <= words.length <= 14
1 <= words[i].length <= 15
1 <= letters.length <= 100
letters[i].length == 1
score.length == 26
0 <= score[i] <= 10
words[i], letters[i] contains only lower case English letters.

Solution: Combination

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

C++

// Author: Huahua

class Solution {

public:

int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {

vector<int> counts(26);

vector<int> scores(words.size());

for (char c : letters) ++counts[c - 'a'];

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

for (char c : words[i]) scores[i] += score[c - 'a'];

int ans = 0;

function<void(int, int)> dfs = [&](int s, int cur) {

if (cur > ans) ans = cur;

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

bool valid = true;

for (char c : words[i]) valid &= --counts[c - 'a'] >= 0;

if (valid) dfs(i + 1, cur + scores[i]);

for (char c : words[i]) ++counts[c - 'a'];

}

};

dfs(0, 0);

return ans;

}

};

Huahua's Tech Road

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

Solution: DP

C++

花花酱 LeetCode 1268. Search Suggestions System

Solution 1: Binary Search

C++

Solution 2: Trie

C++

花花酱 LeetCode 1267. Count Servers that Communicate

Solution: Counting

C++

花花酱 LeetCode 1266. Minimum Time Visiting All Points

C++

花花酱 LeetCode 1255. Maximum Score Words Formed by Letters

Solution: Combination

C++