花花酱 LeetCode 648. Replace Words

By zxi on November 8, 2018

Problem

https://leetcode.com/problems/replace-words/description/

In English, we have a concept called root, which can be followed by some other words to form another longer word – let’s call this word successor. For example, the root an, followed by other, which can form another word another.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.

You need to output the sentence after the replacement.

Example 1:

Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Note:

The input will only have lower-case letters.
1 <= dict words number <= 1000
1 <= sentence words number <= 1000
1 <= root length <= 100
1 <= sentence words length <= 1000

Solution 1: HashTable

Time complexity: O(sum(w^2))

Space complexity: O(sum(l))

// Author: Huahua, Running time: 84 ms

class Solution {

public:

string replaceWords(vector<string>& dict, string sentence) {

unordered_set<string> d(begin(dict), end(dict));

sentence.push_back(' ');

string output;

string word;

bool found = false;

for (char c : sentence) {

if (c == ' ') {

if (!output.empty()) output += ' ';

output += word;

word = "";

found = false;

continue;

}

if (found) continue;

word += c;

if (d.count(word)) {

found = true;

}

return output;

}

};

Solution2: Trie

Time complexity: O(sum(l) + n)

Space complexity: O(sum(l) * 26)

// Author: Huahua, running time: 48 ms

class TrieNode {

public:

TrieNode(): children(26), is_word(false) {}

~TrieNode() {

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

if (children[i]) {

delete children[i];

children[i] = nullptr;

}

vector<TrieNode*> children;

bool is_word;

};

class Solution {

public:

string replaceWords(vector<string>& dict, string sentence) {

TrieNode root;

for (const string& word : dict) {

TrieNode* cur = &root;

for (char c : word) {

if (!cur->children[c - 'a']) cur->children[c - 'a'] = new TrieNode();

cur = cur->children[c - 'a'];

}

cur->is_word = true;

}

string ans;

stringstream ss(sentence);

string word;

while (ss >> word) {

TrieNode* cur = &root;

bool found = false;

int len = 0;

for (char c : word) {

cur = cur->children[c - 'a'];

if (!cur) break;

++len;

if (cur->is_word) {

found = true;

break;

}

if (!ans.empty()) ans += ' ';

ans += found ? word.substr(0, len) : word;

}

return ans;

}

};

花花酱 LeetCode 935. Knight Dialer

By zxi on November 4, 2018

Problem

https://leetcode.com/problems/knight-dialer/description/

A chess knight can move as indicated in the chess diagram below:

This time, we place our chess knight on any numbered key of a phone pad (indicated above), and the knight makes N-1 hops. Each hop must be from one key to another numbered key.

Each time it lands on a key (including the initial placement of the knight), it presses the number of that key, pressing N digits total.

How many distinct numbers can you dial in this manner?

Since the answer may be large, output the answer modulo 10^9 + 7.

Example 1:

Input: 1
Output: 10

Example 2:

Input: 2
Output: 20

Example 3:

Input: 3
Output: 46

Note:

1 <= N <= 5000

Solution: DP

V1

We can define dp[k][i][j] as # of ways to dial and the last key is (j, i) after k steps

Note: dp[*][3][0], dp[*][3][2] are always zero for all the steps.

Init: dp[0][i][j] = 1

Transition: dp[k][i][j] = sum(dp[k – 1][i + dy][j + dx]) 8 ways of move from last step.

ans = sum(dp[k])

Time complexity: O(kmn) or O(k * 12 * 8) = O(k)

Space complexity: O(kmn) -> O(mn) or O(12*8) = O(1)

V2

define dp[k][i] as # of ways to dial and the last key is i after k steps

init: dp[0][0:10] = 1

transition: dp[k][i] = sum(dp[k-1][j]) that j can move to i

ans: sum(dp[k])

Time complexity: O(k * 10) = O(k)

Space complexity: O(k * 10) -> O(10) = O(1)

C++ V1

// Author: Huahua, 96 ms

class Solution {

public:

int knightDialer(int N) {

constexpr int kMod = 1e9 + 7;

int dirs[8][2] = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};

vector<vector<int>> dp(4, vector<int>(3, 1));

dp[3][0] = dp[3][2] = 0;

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

vector<vector<int>> tmp(4, vector<int>(3));

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

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

if (i == 3 && j != 1) continue;

for (int d = 0; d < 8; ++d) {

int tx = j + dirs[d][0];

int ty = i + dirs[d][1];

if (tx < 0 || ty < 0 || tx >= 3 || ty >= 4) continue;

tmp[i][j] = (tmp[i][j] + dp[ty][tx]) % kMod;

}

dp.swap(tmp);

}

int ans = 0;

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

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

ans = (ans + dp[i][j]) % kMod;

return ans;

}

};

C++ V2

// Author: Huahua, 24 ms

public:

int knightDialer(int N) {

constexpr int kMod = 1e9 + 7;

vector<vector<int>> moves{{4,6},{8,6},{7,9},{4,8},{3,9,0},{},{1,7,0},{2,6},{1,3},{2,4}};

vector<int> dp(10, 1);

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

vector<int> tmp(10);

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

for (int nxt : moves[i])

tmp[nxt] = (tmp[nxt] + dp[i]) % kMod;

dp.swap(tmp);

}

int ans = 0;

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

ans = (ans + dp[i]) % kMod;

return ans;

}

};

Problem

Write a class RecentCounter to count recent requests.

It has only one method: ping(int t), where t represents some time in milliseconds.

Return the number of pings that have been made from 3000 milliseconds ago until now.

Any ping with time in [t - 3000, t] will count, including the current ping.

It is guaranteed that every call to ping uses a strictly larger value of t than before.

Example 1:

Input: inputs = ["RecentCounter","ping","ping","ping","ping"], inputs = [[],[1],[100],[3001],[3002]]
Output: [null,1,2,3,3]

Note:

Each test case will have at most 10000 calls to ping.
Each test case will call ping with strictly increasing values of t.
Each call to ping will have 1 <= t <= 10^9.

Solution: Queue

Use a FIFO queue to track all the previous pings that are within 3000 ms to current.

Time complexity: Avg O(1), Total O(n)

Space complexity: O(n)

C++

class RecentCounter {

public:

RecentCounter() {}

int ping(int t) {

while (!q.empty() && t - q.front() > 3000) q.pop();

q.push(t);

return q.size();

}

private:

queue<int> q;

};

花花酱 LeetCode 934. Shortest Bridge

By zxi on November 4, 2018

Problem

https://leetcode.com/problems/shortest-bridge/description/

In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.)

Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.

Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)

Example 1:

Input: [[0,1],[1,0]]
Output: 1

Example 2:

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

Example 3:

Input: [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1

Note:

1 <= A.length = A[0].length <= 100
A[i][j] == 0 or A[i][j] == 1

Solution: DFS + BFS

Use DFS to find one island and color all the nodes as 2 (BLUE).
Use BFS to find the shortest path from any nodes with color 2 (BLUE) to any nodes with color 1 (RED).

Time complexity: O(mn)

Space complexity: O(mn)

C++

class Solution {

public:

int shortestBridge(vector<vector<int>>& A) {

queue<pair<int, int>> q;

bool found = false;

for (int i = 0; i < A.size() && !found; ++i)

for (int j = 0; j < A[0].size() && !found; ++j)

if (A[i][j]) {

dfs(A, j, i, q);

found = true;

}

int steps = 0;

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

while (!q.empty()) {

size_t size = q.size();

while (size--) {

int x = q.front().first;

int y = q.front().second;

q.pop();

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

int tx = x + dirs[i];

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

if (tx < 0 || ty < 0 || tx >= A[0].size() || ty >= A.size() || A[ty][tx] == 2) continue;

if (A[ty][tx] == 1) return steps;

A[ty][tx] = 2;

q.emplace(tx, ty);

}

++steps;

}

return -1;

}

private:

void dfs(vector<vector<int>>& A, int x, int y, queue<pair<int, int>>& q) {

if (x < 0 || y < 0 || x >= A[0].size() || y >= A.size() || A[y][x] != 1) return;

A[y][x] = 2;

q.emplace(x, y);

dfs(A, x - 1, y, q);

dfs(A, x, y - 1, q);

dfs(A, x + 1, y, q);

dfs(A, x, y + 1, q);

}

};

花花酱 LeetCode 648. Replace Words

Problem

Solution 1: HashTable

Solution2: Trie

花花酱 LeetCode 935. Knight Dialer

Problem

Solution: DP

V1

V2

C++ V1

C++ V2

Related Problem

花花酱 LeetCode 933. Number of Recent Calls

Problem

Solution: Queue

C++

花花酱 LeetCode 934. Shortest Bridge

Problem

Solution: DFS + BFS

C++

Related Problems

花花酱 LeetCode DP Summary 动态规划总结

Category 1.1

Template

Huahua's Tech Road

花花酱 LeetCode 648. Replace Words

Problem

Solution 1: HashTable

Solution2: Trie

花花酱 LeetCode 935. Knight Dialer

Problem

Solution: DP

V1

V2

C++ V1

C++ V2

Related Problem

花花酱 LeetCode 933. Number of Recent Calls

Problem

Solution: Queue

C++

花花酱 LeetCode 934. Shortest Bridge

Problem

Solution: DFS + BFS

C++

Related Problems

花花酱 LeetCode DP Summary 动态规划总结

Category 1.1

Template