Posts tagged as “split”

花花酱 LeetCode 2129. Capitalize the Title

By zxi on January 8, 2022

You are given a string title consisting of one or more words separated by a single space, where each word consists of English letters. Capitalize the string by changing the capitalization of each word such that:

If the length of the word is 1 or 2 letters, change all letters to lowercase.
Otherwise, change the first letter to uppercase and the remaining letters to lowercase.

Return the capitalized title.

Example 1:

Input: title = "capiTalIze tHe titLe"
Output: "Capitalize The Title"
Explanation:
Since all the words have a length of at least 3, the first letter of each word is uppercase, and the remaining letters are lowercase.

Example 2:

Input: title = "First leTTeR of EACH Word"
Output: "First Letter of Each Word"
Explanation:
The word "of" has length 2, so it is all lowercase.
The remaining words have a length of at least 3, so the first letter of each remaining word is uppercase, and the remaining letters are lowercase.

Example 3:

Input: title = "i lOve leetcode"
Output: "i Love Leetcode"
Explanation:
The word "i" has length 1, so it is lowercase.
The remaining words have a length of at least 3, so the first letter of each remaining word is uppercase, and the remaining letters are lowercase.

Constraints:

1 <= title.length <= 100
title consists of words separated by a single space without any leading or trailing spaces.
Each word consists of uppercase and lowercase English letters and is non-empty.

Solution: Straight forward

Without splitting the sentence into words, we need to take care the word of length one and two.

Tips: use std::tolower, std::toupper to transform letters.

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

C++

// Author: Huahua

class Solution {

public:

string capitalizeTitle(string title) {

const int n = title.size();

for (int i = 0; i < title.size(); ++i) {

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

&& i + 2 < n && title[i + 1] != ' ' && title[i + 2] != ' ')

title[i] = toupper(title[i]);

else

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

}

return title;

}

};

Python3

# Author: Huahua

class Solution:

def capitalizeTitle(self, title: str) -> str:

return " ".join(map(lambda w: w.lower() if len(w) <= 2 else w[0].upper() + w[1:].lower(), title.split()))

花花酱 LeetCode 2042. Check if Numbers Are Ascending in a Sentence

By zxi on October 17, 2021

A sentence is a list of tokens separated by a single space with no leading or trailing spaces. Every token is either a positive number consisting of digits 0-9 with no leading zeros, or a word consisting of lowercase English letters.

For example, "a puppy has 2 eyes 4 legs" is a sentence with seven tokens: "2" and "4" are numbers and the other tokens such as "puppy" are words.

Given a string s representing a sentence, you need to check if all the numbers in s are strictly increasing from left to right (i.e., other than the last number, each number is strictly smaller than the number on its right in s).

Return true if so, or false otherwise.

Example 1:

Input: s = "1 box has 3 blue 4 red 6 green and 12 yellow marbles"
Output: true
Explanation: The numbers in s are: 1, 3, 4, 6, 12.
They are strictly increasing from left to right: 1 < 3 < 4 < 6 < 12.

Example 2:

Input: s = "hello world 5 x 5"
Output: false
Explanation: The numbers in s are: 5, 5. They are not strictly increasing.

Example 3:

Input: s = "sunset is at 7 51 pm overnight lows will be in the low 50 and 60 s"
Output: false
Explanation: The numbers in s are: 7, 51, 50, 60. They are not strictly increasing.

Example 4:

Input: s = "4 5 11 26"
Output: true
Explanation: The numbers in s are: 4, 5, 11, 26.
They are strictly increasing from left to right: 4 < 5 < 11 < 26.

Constraints:

3 <= s.length <= 200
s consists of lowercase English letters, spaces, and digits from 0 to 9, inclusive.
The number of tokens in s is between 2 and 100, inclusive.
The tokens in s are separated by a single space.
There are at least two numbers in s.
Each number in s is a positive number less than 100, with no leading zeros.
s contains no leading or trailing spaces.

Solution: String

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

C++

// Author: Huahua

class Solution {

public:

bool areNumbersAscending(string s) {

stringstream ss(s);

string token;

int last = -1;

while (ss >> token) {

if (isdigit(token[0])) {

int num = stoi(token);

if (num <= last) return false;

last = num;

}

return true;

}

};

花花酱 LeetCode 1816. Truncate Sentence

By zxi on April 6, 2021

A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each of the words consists of only uppercase and lowercase English letters (no punctuation).

For example, "Hello World", "HELLO", and "hello world hello world" are all sentences.

You are given a sentence s and an integer k. You want to truncate s such that it contains only the first k words. Return s after truncating it.

Example 1:

Input: s = "Hello how are you Contestant", k = 4
Output: "Hello how are you"
Explanation:
The words in s are ["Hello", "how" "are", "you", "Contestant"].
The first 4 words are ["Hello", "how", "are", "you"].
Hence, you should return "Hello how are you".

Example 2:

Input: s = "What is the solution to this problem", k = 4
Output: "What is the solution"
Explanation:
The words in s are ["What", "is" "the", "solution", "to", "this", "problem"].
The first 4 words are ["What", "is", "the", "solution"].
Hence, you should return "What is the solution".

Example 3:

Input: s = "chopper is not a tanuki", k = 5
Output: "chopper is not a tanuki"

Constraints:

1 <= s.length <= 500
k is in the range [1, the number of words in s].
s consist of only lowercase and uppercase English letters and spaces.
The words in s are separated by a single space.
There are no leading or trailing spaces.

Solution:

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

C++

class Solution {

public:

string truncateSentence(string s, int k) {

string ans;

stringstream ss(s);

for (int i = 0; i < k && ss; ++i) {

string word;

ss >> word;

ans += (ans.empty() ? "" : " ") + word;

}

return ans;

}

};

Python3

class Solution:

def truncateSentence(self, s: str, k: int) -> str:

return " ".join(s.split()[:k])

花花酱 LeetCode 1556. Thousand Separator

By zxi on August 22, 2020

Given an integer n, add a dot (“.”) as the thousands separator and return it in string format.

Example 1:

Input: n = 987
Output: "987"

Example 2:

Input: n = 1234
Output: "1.234"

Example 3:

Input: n = 123456789
Output: "123.456.789"

Example 4:

Input: n = 0
Output: "0"

Constraints:

0 <= n < 2^31

Solution: Digit by digit

Time complexity: O(log^2(n)) -> O(logn)
Space complexity: O(log(n))

C++

class Solution {

public:

string thousandSeparator(int n) {

string ans;

int count = 0;

do {

if (count++ % 3 == 0 && ans.size())

ans = "." + ans;

ans = to_string(n % 10) + ans;

n /= 10;

} while (n);

return ans;

}

};

花花酱 LeetCode 1507. Reformat Date

By zxi on July 11, 2020

Given a date string in the form Day Month Year, where:

Day is in the set {"1st", "2nd", "3rd", "4th", ..., "30th", "31st"}.
Month is in the set {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"}.
Year is in the range [1900, 2100].

Convert the date string to the format YYYY-MM-DD, where:

YYYY denotes the 4 digit year.
MM denotes the 2 digit month.
DD denotes the 2 digit day.

Example 1:

Input: date = "20th Oct 2052"
Output: "2052-10-20"

Example 2:

Input: date = "6th Jun 1933"
Output: "1933-06-06"

Example 3:

Input: date = "26th May 1960"
Output: "1960-05-26"

Constraints:

The given dates are guaranteed to be valid, so no error handling is necessary.

Solution: String + HashTable

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

C++

// Author: Huahua

class Solution {

public:

string reformatDate(string date) {

stringstream ss(date);

string day, month, year;

ss >> day >> month >> year;

unordered_map<string, string> m{{"Jan", "01"},

{"Feb", "02"},

{"Mar", "03"},

{"Apr", "04"},

{"May", "05"},

{"Jun", "06"},

{"Jul", "07"},

{"Aug", "08"},

{"Sep", "09"},

{"Oct", "10"},

{"Nov", "11"},

{"Dec", "12"}};

day = day.substr(0, day.length() - 2);

if (day.length() == 1) day = "0" + day;

return year + "-" + m[month] + "-" + day;

}

};

Java

// Author: Huahua

class Solution {

public String reformatDate(String date) {

Map<String, String> m = new HashMap<String, String>();

m.put("Jan", "01");

m.put("Feb", "02");

m.put("Mar", "03");

m.put("Apr", "04");

m.put("May", "05");

m.put("Jun", "06");

m.put("Jul", "07");

m.put("Aug", "08");

m.put("Sep", "09");

m.put("Oct", "10");

m.put("Nov", "11");

m.put("Dec", "12");

String[] items = date.split(" ");

String day = items[0].substring(0, items[0].length() - 2);

if (day.length() == 1) day = "0" + day;

return items[2] + "-" + m.get(items[1]) + "-" + day;

}

Python

# Author: Huahua

class Solution:

def reformatDate(self, date: str) -> str:

m = {"Jan": "01", "Feb": "02", "Mar": "03",

"Apr": "04", "May": "05", "Jun": "06",

"Jul": "07", "Aug": "08", "Sep": "09",

"Oct": "10", "Nov": "11", "Dec": "12"}

items = date.split(" ")

day = items[0][:-2]

if len(day) == 1: day = "0" + day

return items[2] + "-" + m[items[1]] + "-" + day