Huahua’s Tech Road

花花酱 LeetCode 1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence

By zxi on May 23, 2020

Given a sentence that consists of some words separated by a single space, and a searchWord.

You have to check if searchWord is a prefix of any word in sentence.

Return the index of the word in sentence where searchWord is a prefix of this word (1-indexed).

If searchWord is a prefix of more than one word, return the index of the first word (minimum index). If there is no such word return -1.

A prefix of a string S is any leading contiguous substring of S.

Example 1:

Input: sentence = "i love eating burger", searchWord = "burg"
Output: 4
Explanation: "burg" is prefix of "burger" which is the 4th word in the sentence.

Example 2:

Input: sentence = "this problem is an easy problem", searchWord = "pro"
Output: 2
Explanation: "pro" is prefix of "problem" which is the 2nd and the 6th word in the sentence, but we return 2 as it's the minimal index.

Example 3:

Input: sentence = "i am tired", searchWord = "you"
Output: -1
Explanation: "you" is not a prefix of any word in the sentence.

Example 4:

Input: sentence = "i use triple pillow", searchWord = "pill"
Output: 4

Example 5:

Input: sentence = "hello from the other side", searchWord = "they"
Output: -1

Constraints:

1 <= sentence.length <= 100
1 <= searchWord.length <= 10
sentence consists of lowercase English letters and spaces.
searchWord consists of lowercase English letters.

Solution 1: Brute Force

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

C++

class Solution {

public:

int isPrefixOfWord(string sentence, string searchWord) {

const int n = sentence.size();

const int l = searchWord.size();

int word = 0;

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

if (i == 0 || sentence[i - 1] == ' ') {

++word;

bool valid = true;

for (int j = 0; j < l && valid; ++j)

valid = valid && (sentence[i + j] == searchWord[j]);

if (valid) return word;

}

return -1;

}

};

f-String in Python3

By zxi on May 19, 2020

Example code

name = 'Huahua'

score = 123.456789

print('name = ' + name + ', score = ' + str(score))

print('name = %s, score = %.3f' % (name, score))

print('name = {name}, score = {score:.3f}'.format(name=name, score=score))

print('name = {name}, score = {score:.3f}'.format(name='Huahua', score=123.456789))

print(f'name = {name}, score = {score:.3f}') # Python 3.6

print(f'{name = }, {score = :.3f}') # Python 3.8

def add(a, b):

return a + b

k = 1

print(f'{k = }, {add(k, 2) = }') # k = 1, add(k, 2) = 3

花花酱 LeetCode 1449. Form Largest Integer With Digits That Add up to Target

By zxi on May 18, 2020

Given an array of integers cost and an integer target. Return the maximum integer you can paint under the following rules:

The cost of painting a digit (i+1) is given by cost[i] (0 indexed).
The total cost used must be equal to target.
Integer does not have digits 0.

Since the answer may be too large, return it as string.

If there is no way to paint any integer given the condition, return “0”.

Example 1:

Input: cost = [4,3,2,5,6,7,2,5,5], target = 9
Output: "7772"
Explanation:  The cost to paint the digit '7' is 2, and the digit '2' is 3. Then cost("7772") = 2*3+ 3*1 = 9. You could also paint "997", but "7772" is the largest number.
Digit    cost
  1  ->   4
  2  ->   3
  3  ->   2
  4  ->   5
  5  ->   6
  6  ->   7
  7  ->   2
  8  ->   5
  9  ->   5

Example 2:

Input: cost = [7,6,5,5,5,6,8,7,8], target = 12
Output: "85"
Explanation: The cost to paint the digit '8' is 7, and the digit '5' is 5. Then cost("85") = 7 + 5 = 12.

Example 3:

Input: cost = [2,4,6,2,4,6,4,4,4], target = 5
Output: "0"
Explanation: It's not possible to paint any integer with total cost equal to target.

Example 4:

Input: cost = [6,10,15,40,40,40,40,40,40], target = 47
Output: "32211"

Constraints:

cost.length == 9
1 <= cost[i] <= 5000
1 <= target <= 5000

Solution: DP

dp(target) := largest number to print with cost == target.
dp(target) = max(dp(target – d) + cost[d])

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

C++ / Top Down

// Author: Huahua, 280 ms

class Solution {

public:

string largestNumber(vector<int>& cost, int target) {

vector<string> cache(target + 1);

// dp[i] := largestNumber that has cost i.

function<string(int)> dp = [&](int t) -> string {

if (t < 0) return "0"; // Invalid.

if (t == 0) return ""; // Found a solution.

if (!cache[t].empty()) return cache[t];

cache[t] = "0"; // Important !!!

for (int d = 1; d <= 9; ++d) {

const string& cur = dp(t - cost[d - 1]);

if (cur != "0" && cur.length() + 1 >= cache[t].length())

cache[t] = to_string(d) + cur;

}

return cache[t];

};

return dp(target);

}

};

C++ / Bottom Up

// Author: Huahua, 240 ms

class Solution {

public:

string largestNumber(vector<int>& cost, int target) {

// dp[i] := largestNumber that has cost i.

vector<string> dp(target + 1, "0");

dp[0] = "";

for (int t = 1; t <= target; ++t)

for (int d = 1; d <= 9; ++d) {

const int s = t - cost[d - 1];

if (s < 0 || dp[s] == "0"

|| dp[s].length() + 1 < dp[t].length()) continue;

dp[t] = to_string(d) + dp[s];

}

return dp[target];

}

};

To avoid string copying, we can store digit added (in order to back track the parent) and length of the optimal string.

Time complexity: O(target)
Space complexity: O(target)

C++ / O(target)

// Author: Huahua, 25 ms

class Solution {

public:

string largestNumber(vector<int>& cost, int target) {

vector<pair<int, int>> cache(target + 1, {-1, -1});

// dp[i] := {digit, length} of largestNumber that has cost i.

function<pair<int, int>(int)> dp = [&](int t) -> pair<int, int> {

if (t < 0) return {0, -1}; // Invalid.

if (t == 0) return {0, 0}; // Found a solution.

if (cache[t].first != -1) return cache[t];

cache[t] = {0, -1}; // make as solved but invalid.

for (int d = 1; d <= 9; ++d) {

const int l = dp(t - cost[d - 1]).second;

if (l != -1 && l + 1 >= cache[t].second)

cache[t] = {d, l + 1};

}

return cache[t];

};

dp(target);

if (cache[target].second <= 0) return "0";

string ans;

while (target) {

ans += cache[target].first + '0';

target -= cost[cache[target].first - 1];

}

return ans;

}

};

C++ / O(target)

// Author: Huahua, 28 ms

class Solution {

public:

string largestNumber(vector<int>& cost, int target) {

// dp[i] = {d, length} of the largest number that costs i.

vector<pair<int, int>> dp(target + 1, {-1, -1});

dp[0] = {0, 0};

for (int t = 1; t <= target; ++t)

for (int d = 1; d <= 9; ++d) {

const int s = t - cost[d - 1];

if (s < 0 || dp[s].second == -1

|| dp[s].second + 1 < dp[t].second) continue;

dp[t] = {d, dp[s].second + 1};

}

if (dp[target].second == -1) return "0";

string ans;

while (target) {

ans += dp[target].first + '0';

target -= cost[dp[target].first - 1];

}

return ans;

}

};

花花酱 LeetCode 1448. Count Good Nodes in Binary Tree

By zxi on May 17, 2020

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Example 1:

Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.

Example 2:

Input: root = [3,3,null,4,2]
Output: 3
Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.

Example 3:

Input: root = [1]
Output: 1
Explanation: Root is considered as good.

Constraints:

The number of nodes in the binary tree is in the range [1, 10^5].
Each node’s value is between [-10^4, 10^4].

Solution: Recursion

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

C++

// Author: Huahua

class Solution {

public:

int goodNodes(TreeNode* root, int max_val = INT_MIN) {

if (!root) return 0;

return goodNodes(root->left, max(max_val, root->val))

+ goodNodes(root->right, max(max_val, root->val))

+ (root->val >= max_val ? 1 : 0);

}

};

花花酱 LeetCode 1447. Simplified Fractions

By zxi on May 17, 2020

Given an integer n, return a list of all simplified fractions between 0 and 1 (exclusive) such that the denominator is less-than-or-equal-to n. The fractions can be in any order.

Example 1:

Input: n = 2
Output: ["1/2"]
Explanation: "1/2" is the only unique fraction with a denominator less-than-or-equal-to 2.

Example 2:

Input: n = 3
Output: ["1/2","1/3","2/3"]

Example 3:

Input: n = 4
Output: ["1/2","1/3","1/4","2/3","3/4"]
Explanation: "2/4" is not a simplified fraction because it can be simplified to "1/2".

Example 4:

Input: n = 1
Output: []

Constraints:

1 <= n <= 100

Solution: GCD

if gcd(a, b) == 1 then a/b is a simplified frication.

std::gcd is available since c++17.

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

C++

// Author: Huahua

class Solution {

public:

vector<string> simplifiedFractions(int n) {

vector<string> ans;

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

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

if (gcd(i, j) == 1)

ans.push_back(to_string(i) + "/" + to_string(j));

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence

Solution 1: Brute Force

C++

f-String in Python3

Example code

花花酱 LeetCode 1449. Form Largest Integer With Digits That Add up to Target

Solution: DP

C++ / Top Down

C++ / Bottom Up

C++ / O(target)

C++ / O(target)

花花酱 LeetCode 1448. Count Good Nodes in Binary Tree

Solution: Recursion

C++

花花酱 LeetCode 1447. Simplified Fractions

Solution: GCD

C++