Posts tagged as “string”

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

}

};

花花酱 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 1446. Consecutive Characters

By zxi on May 17, 2020

Given a string s, the power of the string is the maximum length of a non-empty substring that contains only one unique character.

Return the power of the string.

Example 1:

Input: s = "leetcode"
Output: 2
Explanation: The substring "ee" is of length 2 with the character 'e' only.

Example 2:

Input: s = "abbcccddddeeeeedcba"
Output: 5
Explanation: The substring "eeeee" is of length 5 with the character 'e' only.

Example 3:

Input: s = "triplepillooooow"
Output: 5

Example 4:

Input: s = "hooraaaaaaaaaaay"
Output: 11

Example 5:

Input: s = "tourist"
Output: 1

Constraints:

1 <= s.length <= 500
s contains only lowercase English letters.

Solution: Run length encoding?

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

C++

// Author: Huahua

class Solution {

public:

int maxPower(string s) {

char p = '?';

int ans = 0;

int cur = 0;

for (char c : s) {

if (c != p) cur = 0;

p = c;

ans = max(ans, ++cur);

}

return ans;

}

};

花花酱 LeetCode 1451. Rearrange Words in a Sentence

By zxi on May 16, 2020

Given a sentence text (A sentence is a string of space-separated words) in the following format:

First letter is in upper case.
Each word in text are separated by a single space.

Your task is to rearrange the words in text such that all words are rearranged in an increasing order of their lengths. If two words have the same length, arrange them in their original order.

Return the new text following the format shown above.

Example 1:

Input: text = "Leetcode is cool"
Output: "Is cool leetcode"
Explanation: There are 3 words, "Leetcode" of length 8, "is" of length 2 and "cool" of length 4.
Output is ordered by length and the new first word starts with capital letter.

Example 2:

Input: text = "Keep calm and code on"
Output: "On and keep calm code"
Explanation: Output is ordered as follows:
"On" 2 letters.
"and" 3 letters.
"keep" 4 letters in case of tie order by position in original text.
"calm" 4 letters.
"code" 4 letters.

Example 3:

Input: text = "To be or not to be"
Output: "To be or to be not"

Constraints:

text begins with a capital letter and then contains lowercase letters and single space between words.
1 <= text.length <= 10^5

Solution: Stable sort

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

C++

// Author: Huahua

class Solution {

public:

string arrangeWords(string text) {

vector<string> words{""};

for (char c : text) {

if (c == ' ')

words.push_back("");

else

words.back() += c;

}

words[0][0] = tolower(words[0][0]);

stable_sort(begin(words), end(words), [](const auto& w1, const auto& w2){

return w1.length() < w2.length();

});

string ans;

for (const string& word : words) {

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

ans += word;

}

ans[0] = toupper(ans[0]);

return ans;

}

};

花花酱 LeetCode 1419. Minimum Number of Frogs Croaking

By zxi on April 20, 2020

Given the string croakOfFrogs, which represents a combination of the string “croak” from different frogs, that is, multiple frogs can croak at the same time, so multiple “croak” are mixed. Return the minimum number of different frogs to finish all the croak in the given string.

A valid “croak” means a frog is printing 5 letters ‘c’, ’r’, ’o’, ’a’, ’k’ sequentially. The frogs have to print all five letters to finish a croak. If the given string is not a combination of valid “croak” return -1.

Example 1:

Input: croakOfFrogs = "croakcroak"
Output: 1 
Explanation: One frog yelling "croak" twice.

Example 2:

Input: croakOfFrogs = "crcoakroak"
Output: 2 
Explanation: The minimum number of frogs is two. 
The first frog could yell "crcoakroak".
The second frog could yell later "crcoakroak".

Example 3:

Input: croakOfFrogs = "croakcrook"
Output: -1
Explanation: The given string is an invalid combination of "croak" from different frogs.

Example 4:

Input: croakOfFrogs = "croakcroa"
Output: -1

Constraints:

1 <= croakOfFrogs.length <= 10^5
All characters in the string are: 'c', 'r', 'o', 'a' or 'k'.

Solution: Hashtable

Count the frequency of the letters, we need to make sure f[c] >= f[r] >= f[o] >= f[a] >= f[k] holds all the time, otherwise return -1.
whenever encounter c, increase the current frog, whenever there is k, decrease the frog count.
Don’t forget to check the current frog number, should be 0 in the end, otherwise there are open letters.

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

C++

// Author: Huahua

class Solution {

public:

int minNumberOfFrogs(string croakOfFrogs) {

vector<int> idx(26);

idx['c' - 'a'] = 0;

idx['r' - 'a'] = 1;

idx['o' - 'a'] = 2;

idx['a' - 'a'] = 3;

idx['k' - 'a'] = 4;

vector<int> count(5);

int cur = 0;

int ans = 0;

for (char ch : croakOfFrogs) {

const int i = idx[ch - 'a'];

++count[i];

if (ch == 'c') {

ans = max(ans, ++cur);

continue;

}

if (count[i] > count[i - 1]) return -1;

if (ch == 'k') --cur;

}

return cur ? -1 : ans;

}

};