Posts published in “String”

花花酱 LeetCode 2108. Find First Palindromic String in the Array

By zxi on December 20, 2021

Given an array of strings words, return the first palindromic string in the array. If there is no such string, return an empty string "".

A string is palindromic if it reads the same forward and backward.

Example 1:

Input: words = ["abc","car","ada","racecar","cool"]
Output: "ada"
Explanation: The first string that is palindromic is "ada".
Note that "racecar" is also palindromic, but it is not the first.

Example 2:

Input: words = ["notapalindrome","racecar"]
Output: "racecar"
Explanation: The first and only string that is palindromic is "racecar".

Example 3:

Input: words = ["def","ghi"]
Output: ""
Explanation: There are no palindromic strings, so the empty string is returned.

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists only of lowercase English letters.

Solution: Brute Force

Enumerate each word and check whether it’s a palindrome or not.

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

C++

// Author: Huahua

class Solution {

public:

string firstPalindrome(vector<string>& words) {

auto isPalindrome = [](string_view s) {

size_t l = s.size();

for (size_t i = 0; i < l / 2; ++i)

if (s[i] != s[l - i - 1]) return false;

return true;

};

for (const string& word : words)

if (isPalindrome(word)) return word;

return "";

}

};

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

}

};

花花酱 LeetCode 2063. Vowels of All Substrings

By zxi on November 7, 2021

Given a string word, return the sum of the number of vowels ('a', 'e', 'i', 'o', and 'u') in every substring of word.

A substring is a contiguous (non-empty) sequence of characters within a string.

Note: Due to the large constraints, the answer may not fit in a signed 32-bit integer. Please be careful during the calculations.

Example 1:

Input: word = "aba"
Output: 6
Explanation: 
All possible substrings are: "a", "ab", "aba", "b", "ba", and "a".
- "b" has 0 vowels in it
- "a", "ab", "ba", and "a" have 1 vowel each
- "aba" has 2 vowels in it
Hence, the total sum of vowels = 0 + 1 + 1 + 1 + 1 + 2 = 6.

Example 2:

Input: word = "abc"
Output: 3
Explanation: 
All possible substrings are: "a", "ab", "abc", "b", "bc", and "c".
- "a", "ab", and "abc" have 1 vowel each
- "b", "bc", and "c" have 0 vowels each
Hence, the total sum of vowels = 1 + 1 + 1 + 0 + 0 + 0 = 3.

Example 3:

Input: word = "ltcd"
Output: 0
Explanation: There are no vowels in any substring of "ltcd".

Example 4:

Input: word = "noosabasboosa"
Output: 237
Explanation: There are a total of 237 vowels in all the substrings.

Constraints:

1 <= word.length <= 10⁵
word consists of lowercase English letters.

Solution: Math

For a vowel at index i,
we can choose 0, 1, … i as starting point
choose i, i+1, …, n -1 as end point.
There will be (i – 0 + 1) * (n – 1 – i + 1) possible substrings that contains word[i].

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

C++

class Solution {

public:

long long countVowels(string word) {

const long long n = word.size();

long long ans = 0;

for (long long i = 0; i < n; ++i) {

switch (word[i]) {

case 'a':

case 'e':

case 'i':

case 'o':

case 'u':

ans += (i + 1) * (n - 1 - i + 1);

break;

}

return ans;

}

};