Posts tagged as “string”

花花酱 LeetCode 1417. Reformat The String

By zxi on April 20, 2020

Given alphanumeric string s. (Alphanumeric string is a string consisting of lowercase English letters and digits).

You have to find a permutation of the string where no letter is followed by another letter and no digit is followed by another digit. That is, no two adjacent characters have the same type.

Return the reformatted string or return an empty string if it is impossible to reformat the string.

Example 1:

Input: s = "a0b1c2"
Output: "0a1b2c"
Explanation: No two adjacent characters have the same type in "0a1b2c". "a0b1c2", "0a1b2c", "0c2a1b" are also valid permutations.

Example 2:

Input: s = "leetcode"
Output: ""
Explanation: "leetcode" has only characters so we cannot separate them by digits.

Example 3:

Input: s = "1229857369"
Output: ""
Explanation: "1229857369" has only digits so we cannot separate them by characters.

Example 4:

Input: s = "covid2019"
Output: "c2o0v1i9d"

Example 5:

Input: s = "ab123"
Output: "1a2b3"

Constraints:

1 <= s.length <= 500
s consists of only lowercase English letters and/or digits.

Solution: Two streams

Create two stacks, one for alphas, another for numbers. If the larger stack has more than one element than the other one then no solution, return “”. Otherwise, interleave two stacks, start with the larger one.

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

C++

// Author: Huahua

class Solution {

public:

string reformat(string s) {

string q1;

string q2;

for (char c : s) {

if (isalpha(c))

q1 += c;

else

q2 += c;

}

if (q1.length() < q2.length())

swap(q1, q2);

if (q1.length() > q2.length() + 1)

return "";

string ans;

while (!q1.empty()) {

ans += q1.back();

q1.pop_back();

if (q2.empty()) break;

ans += q2.back();

q2.pop_back();

}

return ans;

}

};

花花酱 LeetCode 1416. Restore The Array

By zxi on April 18, 2020

A program was supposed to print an array of integers. The program forgot to print whitespaces and the array is printed as a string of digits and all we know is that all integers in the array were in the range [1, k] and there are no leading zeros in the array.

Given the string s and the integer k. There can be multiple ways to restore the array.

Return the number of possible array that can be printed as a string s using the mentioned program.

The number of ways could be very large so return it modulo 10^9 + 7

Example 1:

Input: s = "1000", k = 10000
Output: 1
Explanation: The only possible array is [1000]

Example 2:

Input: s = "1000", k = 10
Output: 0
Explanation: There cannot be an array that was printed this way and has all integer >= 1 and <= 10.

Example 3:

Input: s = "1317", k = 2000
Output: 8
Explanation: Possible arrays are [1317],[131,7],[13,17],[1,317],[13,1,7],[1,31,7],[1,3,17],[1,3,1,7]

Example 4:

Input: s = "2020", k = 30
Output: 1
Explanation: The only possible array is [20,20]. [2020] is invalid because 2020 > 30. [2,020] is ivalid because 020 contains leading zeros.

Example 5:

Input: s = "1234567890", k = 90
Output: 34

Constraints:

1 <= s.length <= 10^5.
s consists of only digits and doesn’t contain leading zeros.
1 <= k <= 10^9.

Solution: DP

dp[i] := # of ways to restore the array for s[i:n].

dp[i] = sum(dp[j]), where 0 < j < n, int(s[i:j]) <= k, s[i] != 0

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

Top-down

C++

// Author: Huahua

class Solution {

public:

int numberOfArrays(string s, int k) {

constexpr int kMod = 1e9 + 7;

const int n = s.length();

vector<int> mem(n, -1);

// dp(i) returns # of ways for s[i:n]

function<int(int)> dp = [&](int i) {

if (i == n) return 1;

if (s[i] == '0') return 0;

if (mem[i] >= 0) return mem[i];

long num = 0;

int ans = 0;

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

num = num * 10 + (s[j - 1] - '0');

if (num > k) break;

ans = (ans + dp(j)) % kMod;

}

return mem[i] = ans;

};

return dp(0);

}

};

bottom-up

C++

// Author: Huahua

class Solution {

public:

int numberOfArrays(string s, int k) {

constexpr int kMod = 1e9 + 7;

const int n = s.length();

vector<int> dp(n + 1); // # of ways for s[i:n]

dp.back() = 1;

for (int i = n - 1; i >= 0; --i) {

if (s[i] == '0') continue;

long num = 0;

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

num = num * 10 + (s[j - 1] - '0');

if (num > k) break;

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

}

return dp[0];

}

};

花花酱 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 1410. HTML Entity Parser

By zxi on April 11, 2020

HTML entity parser is the parser that takes HTML code as input and replace all the entities of the special characters by the characters itself.

The special characters and their entities for HTML are:

Quotation Mark: the entity is " and symbol character is ".
Single Quote Mark: the entity is ' and symbol character is '.
Ampersand: the entity is & and symbol character is &.
Greater Than Sign: the entity is > and symbol character is >.
Less Than Sign: the entity is < and symbol character is <.
Slash: the entity is &frasl; and symbol character is /.

Given the input text string to the HTML parser, you have to implement the entity parser.

Return the text after replacing the entities by the special characters.

Example 1:

Input: text = "&amp; is an HTML entity but &ambassador; is not."
Output: "& is an HTML entity but &ambassador; is not."
Explanation: The parser will replace the &amp; entity by &

Example 2:

Input: text = "and I quote: &quot;...&quot;"
Output: "and I quote: \"...\""

Example 3:

Input: text = "Stay home! Practice on Leetcode :)"
Output: "Stay home! Practice on Leetcode :)"

Example 4:

Input: text = "x &gt; y &amp;&amp; x &lt; y is always false"
Output: "x > y && x < y is always false"

Example 5:

Input: text = "leetcode.com&frasl;problemset&frasl;all"
Output: "leetcode.com/problemset/all"

Constraints:

1 <= text.length <= 10^5
The string may contain any possible characters out of all the 256 ASCII characters.

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

string entityParser(string text) {

map<string, string> m{

{""", "\""}, {"'", "'"}, {"&", "&"},

{">", ">"}, {"<", "<"}, {"&frasl;", "/"}};

string ans;

string buf;

for (char c : text) {

buf += c;

if (buf.back() != ';') continue;

const int l = buf.size();

for (const auto& [k, v] : m) {

const int kl = k.length();

if (l >= kl && buf.substr(l - kl) == k) {

ans += buf.substr(0, l - kl) + v;

buf.clear();

break;

}

return ans + buf;

}

};

花花酱 LeetCode 1408. String Matching in an Array

By zxi on April 11, 2020

Given an array of string words. Return all strings in words which is substring of another word in any order.

String words[i] is substring of words[j], if can be obtained removing some characters to left and/or right side of words[j].

Example 1:

Input: words = ["mass","as","hero","superhero"]
Output: ["as","hero"]
Explanation: "as" is substring of "mass" and "hero" is substring of "superhero".
["hero","as"] is also a valid answer.

Example 2:

Input: words = ["leetcode","et","code"]
Output: ["et","code"]
Explanation: "et", "code" are substring of "leetcode".

Example 3:

Input: words = ["blue","green","bu"]
Output: []

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 30
words[i] contains only lowercase English letters.
It’s guaranteed that words[i] will be unique.

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

vector<string> stringMatching(vector<string>& words) {

vector<string> ans;

const int n = words.size();

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

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

if (i == j) continue;

if (words[j].find(words[i]) != string::npos) {

ans.push_back(words[i]);

break;

}

return ans;

}

};