Posts tagged as “string”

花花酱 LeetCode 166. Fraction to Recurring Decimal

By zxi on November 28, 2021

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

If multiple answers are possible, return any of them.

It is guaranteed that the length of the answer string is less than 10⁴ for all the given inputs.

Example 1:

Input: numerator = 1, denominator = 2
Output: "0.5"

Example 2:

Input: numerator = 2, denominator = 1
Output: "2"

Example 3:

Input: numerator = 2, denominator = 3
Output: "0.(6)"

Example 4:

Input: numerator = 4, denominator = 333
Output: "0.(012)"

Example 5:

Input: numerator = 1, denominator = 5
Output: "0.2"

Constraints:

-2³¹ <= numerator, denominator <= 2³¹ - 1
denominator != 0

Solution: Hashtable

Time complexity: O(?)

C++

// Author: Huahua

class Solution {

public:

string fractionToDecimal(int numerator, int denominator) {

stringstream ss,ss2;

long long n = numerator;

long long d = denominator;

if ( n > 0 && d < 0 || n < 0 && d > 0) {

ss << "-";

n = abs(n);

d = abs(d);

}

ss << (n / d);

long long r = n % d;

bool loop = false;

int count = 0;

int loop_start;

if (r) {

n = r;

ss << ".";

unordered_map<int, int> rs;

rs[r] = 0;

while (r) {

n = n*10;

r = n % d;

ss2 << (n / d);

n = r;

if (r && rs.count(r)) {

loop = true;

loop_start = rs[r];

break;

}

rs[r] = ++count;

}

if (loop) {

auto s2 = ss2.str();

ss << s2.substr(0, loop_start) << "(" << s2.substr(loop_start) << ")";

} else {

ss << ss2.str();

}

return ss.str();

}

};

花花酱 LeetCode 151. Reverse Words in a String

By zxi on November 28, 2021

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Example 4:

Input: s = "  Bob    Loves  Alice   "
Output: "Alice Loves Bob"

Example 5:

Input: s = "Alice does not even like bob"
Output: "bob like even not does Alice"

Constraints:

1 <= s.length <= 10⁴
s contains English letters (upper-case and lower-case), digits, and spaces ' '.
There is at least one word in s.

Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

Solution: Stack

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

C++

// Author: Huahua

class Solution {

public:

string reverseWords(string s) {

stringstream ss(s);

stack<string> st;

string w;

while (ss >> w)

st.push(w);

string ans;

while (!st.empty()) {

ans += st.top();

st.pop();

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

}

return ans;

}

};

Solution: In-Place

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

C++

// Author: Huahua

class Solution {

public:

string reverseWords(string& s) {

reverse(begin(s), end(s));

int l = 0;

for (int i = 0, j = 0; i < s.length(); ++i) {

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

if (l) ++l;

j = i;

while (j < s.length() && s[j] != ' ') ++j;

reverse(begin(s) + l, begin(s) + j);

l += (j - i);

i = j;

}

s.resize(l);

return s;

}

};

花花酱 LeetCode 65. Valid Number

By zxi on November 26, 2021

A valid number can be split up into these components (in order):

A decimal number or an integer.
(Optional) An 'e' or 'E', followed by an integer.

A decimal number can be split up into these components (in order):

(Optional) A sign character (either '+' or '-').
One of the following formats:
1. One or more digits, followed by a dot '.'.
2. One or more digits, followed by a dot '.', followed by one or more digits.
3. A dot '.', followed by one or more digits.

An integer can be split up into these components (in order):

(Optional) A sign character (either '+' or '-').
One or more digits.

For example, all the following are valid numbers: ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"], while the following are not valid numbers: ["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"].

Given a string s, return true if s is a valid number.

Example 1:

Input: s = "0"
Output: true

Example 2:

Input: s = "e"
Output: false

Example 3:

Input: s = "."
Output: false

Example 4:

Input: s = ".1"
Output: true

Constraints:

1 <= s.length <= 20
s consists of only English letters (both uppercase and lowercase), digits (0-9), plus '+', minus '-', or dot '.'.

Solution: Rule checking

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

C++

// Author: Huahua

class Solution {

public:

bool isNumber(string s) {

for (int i = 0; i < s.length(); ++i)

if (s[i] != ' ') {

s = s.substr(i);

break;

}

while (!s.empty() && s.back() == ' ') s.pop_back();

bool dot = false;

bool e = false;

bool digit = false;

for (int i = 0; i < s.length(); ++i) {

s[i] = tolower(s[i]);

if (isdigit(s[i])) {

digit = true;

} else if (s[i] == '.') {

if (e || dot) return false;

dot = true;

} else if (s[i] == 'e') {

if (e || !digit) return false;

e = true;

digit = false;

} else if (s[i] == '-' || s[i] == '+') {

if (i != 0 && s[i - 1] != 'e')

return false;

} else {

return false;

}

return digit;

}

};

花花酱 LeetCode 30. Substring with Concatenation of All Words

By zxi on November 26, 2021

You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

You can return the answer in any order.

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]

Constraints:

1 <= s.length <= 10⁴
s consists of lower-case English letters.
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] consists of lower-case English letters.

Solution: Hashtable + Brute Force

Try every index and use a hashtable to check coverage.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> findSubstring(string_view s, vector<string>& words) {

const int n = s.length();

const int m = words.size();

const int l = words[0].size();

if (m * l > n) return {};

unordered_map<string_view, int> freq;

for (const string& word : words) ++freq[word];

vector<int> ans;

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

unordered_map<string_view, int> seen;

int count = 0;

for (int k = 0; k < m; ++k) {

string_view t = s.substr(i + k * l, l);

auto it = freq.find(t);

if (it == end(freq)) break;

if (++seen[t] > it->second) break;

++count;

}

if (count == m) ans.push_back(i);

}

return ans;

}

};

花花酱 LeetCode 2000. Reverse Prefix of Word

By zxi on November 20, 2021

Given a 0-indexed string word and a character ch, reverse the segment of word that starts at index 0 and ends at the index of the first occurrence of ch (inclusive). If the character ch does not exist in word, do nothing.

For example, if word = "abcdefd" and ch = "d", then you should reverse the segment that starts at 0 and ends at 3 (inclusive). The resulting string will be "dcbaefd".

Return the resulting string.

Example 1:

Input: word = "abcdefd", ch = "d"
Output: "dcbaefd"
Explanation: The first occurrence of "d" is at index 3. 
Reverse the part of word from 0 to 3 (inclusive), the resulting string is "dcbaefd".

Example 2:

Input: word = "xyxzxe", ch = "z"
Output: "zxyxxe"
Explanation: The first and only occurrence of "z" is at index 3.
Reverse the part of word from 0 to 3 (inclusive), the resulting string is "zxyxxe".

Example 3:

Input: word = "abcd", ch = "z"
Output: "abcd"
Explanation: "z" does not exist in word.
You should not do any reverse operation, the resulting string is "abcd".

Constraints:

1 <= word.length <= 250
word consists of lowercase English letters.
ch is a lowercase English letter.

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

string reversePrefix(string word, char ch) {

for (size_t i = 0; i < word.size(); ++i)

if (word[i] == ch) return

string(rbegin(word) + word.size() - i - 1, rend(word)) + word.substr(i + 1);

return word;

}

};