Posts tagged as “string”

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

花花酱 LeetCode 1487. Making File Names Unique

By zxi on June 20, 2020

Given an array of strings names of size n. You will create n folders in your file system such that, at the ith minute, you will create a folder with the name names[i].

Since two files cannot have the same name, if you enter a folder name which is previously used, the system will have a suffix addition to its name in the form of (k), where, k is the smallest positive integer such that the obtained name remains unique.

Return an array of strings of length n where ans[i] is the actual name the system will assign to the ith folder when you create it.

Example 1:

Input: names = ["pes","fifa","gta","pes(2019)"]
Output: ["pes","fifa","gta","pes(2019)"]
Explanation: Let's see how the file system creates folder names:
"pes" --> not assigned before, remains "pes"
"fifa" --> not assigned before, remains "fifa"
"gta" --> not assigned before, remains "gta"
"pes(2019)" --> not assigned before, remains "pes(2019)"

Example 2:

Input: names = ["gta","gta(1)","gta","avalon"]
Output: ["gta","gta(1)","gta(2)","avalon"]
Explanation: Let's see how the file system creates folder names:
"gta" --> not assigned before, remains "gta"
"gta(1)" --> not assigned before, remains "gta(1)"
"gta" --> the name is reserved, system adds (k), since "gta(1)" is also reserved, systems put k = 2. it becomes "gta(2)"
"avalon" --> not assigned before, remains "avalon"

Example 3:

Input: names = ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece"]
Output: ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece(4)"]
Explanation: When the last folder is created, the smallest positive valid k is 4, and it becomes "onepiece(4)".

Example 4:

Input: names = ["wano","wano","wano","wano"]
Output: ["wano","wano(1)","wano(2)","wano(3)"]
Explanation: Just increase the value of k each time you create folder "wano".

Example 5:

Input: names = ["kaido","kaido(1)","kaido","kaido(1)"]
Output: ["kaido","kaido(1)","kaido(2)","kaido(1)(1)"]
Explanation: Please note that system adds the suffix (k) to current name even it contained the same suffix before.

Constraints:

1 <= names.length <= 5 * 10^4
1 <= names[i].length <= 20
names[i] consists of lower case English letters, digits and/or round brackets.

Solution: Hashtable

Use a hashtable to store the mapping form base_name to its next suffix index.

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

C++

// Author: Huahua

class Solution {

public:

vector<string> getFolderNames(vector<string>& names) {

vector<string> ans;

unordered_map<string, int> m; // base_name -> next suffix.

for (const string& name : names) {

string unique_name = name;

int j = m[name];

if (j > 0) {

while (m.count(unique_name = name + "(" + to_string(j++) + ")"));

m[name] = j;

}

m[unique_name] = 1;

ans.push_back(unique_name);

}

return ans;

}

};

花花酱 LeetCode 1461. Check If a String Contains All Binary Codes of Size K

By zxi on May 30, 2020

Given a binary string s and an integer k.

Return True if any binary code of length k is a substring of s. Otherwise, return False.

Example 1:

Input: s = "00110110", k = 2
Output: true
Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indicies 0, 1, 3 and 2 respectively.

Example 2:

Input: s = "00110", k = 2
Output: true

Example 3:

Input: s = "0110", k = 1
Output: true
Explanation: The binary codes of length 1 are "0" and "1", it is clear that both exist as a substring.

Example 4:

Input: s = "0110", k = 2
Output: false
Explanation: The binary code "00" is of length 2 and doesn't exist in the array.

Example 5:

Input: s = "0000000001011100", k = 4
Output: false

Constraints:

1 <= s.length <= 5 * 10^5
s consists of 0’s and 1’s only.
1 <= k <= 20

Solution: Hashtable

Insert all possible substrings into a hashtable, the size of the hashtable should be 2^k.

Time complexity: O(n*k)
Space complexity: O(2^k*k) -> O(2^k)

std::string_view: 484 ms, 40.1MB
std::string 644 ms, 58.6MB

C++

// Author: Huahua

// std::string_view: 468 ms, 37.3MB

// std::string: 636 ms, 58.6MB

class Solution {

public:

bool hasAllCodes(string_view s, int k) {

const int n = s.length();

if ((n - k + 1) * k < (1 << k)) return false;

unordered_set<string_view> c;

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

c.insert(s.substr(i, k));

return c.size() == (1 << k);

}

};

花花酱 LeetCode 1456. Maximum Number of Vowels in a Substring of Given Length

By zxi on May 23, 2020

Given a string s and an integer k.

Return the maximum number of vowel letters in any substring of s with length k.

Vowel letters in English are (a, e, i, o, u).

Example 1:

Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.

Example 2:

Input: s = "aeiou", k = 2
Output: 2
Explanation: Any substring of length 2 contains 2 vowels.

Example 3:

Input: s = "leetcode", k = 3
Output: 2
Explanation: "lee", "eet" and "ode" contain 2 vowels.

Example 4:

Input: s = "rhythms", k = 4
Output: 0
Explanation: We can see that s doesn't have any vowel letters.

Example 5:

Input: s = "tryhard", k = 4
Output: 1

Constraints:

1 <= s.length <= 10^5
s consists of lowercase English letters.
1 <= k <= s.length

Solution: Sliding Window

Keep tracking the number of vows in a window of size k.

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

C++

// Author: Huahua

class Solution {

public:

int maxVowels(string s, int k) {

vector<int> v(128);

v['a'] = v['e'] = v['i'] = v['o'] = v['u'] = 1;

int total = 0;

int ans = 0;

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

total += v[s[i - 1]];

if (i >= k) {

ans = max(ans, total);

total -= v[s[i - k]];

}

return ans;

}

};

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

}

};