Posts published in “String”

花花酱 LeetCode 937. Reorder Log Files

By zxi on November 10, 2018

Problem

https://leetcode.com/problems/reorder-log-files/description/

You have an array of logs. Each log is a space delimited string of words.

For each log, the first word in each log is an alphanumeric identifier. Then, either:

Each word after the identifier will consist only of lowercase letters, or;
Each word after the identifier will consist only of digits.

We will call these two varieties of logs letter-logs and digit-logs. It is guaranteed that each log has at least one word after its identifier.

Reorder the logs so that all of the letter-logs come before any digit-log. The letter-logs are ordered lexicographically ignoring identifier, with the identifier used in case of ties. The digit-logs should be put in their original order.

Return the final order of the logs.

Example 1:

Input: ["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]
Output: ["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]

Note:

0 <= logs.length <= 100
3 <= logs[i].length <= 100
logs[i] is guaranteed to have an identifier, and a word after the identifier.

Solution: Partition + Sort

partition the array such that all digit logs are after all letter logs
sort the letter logs part based on the log content

Time complexity: O(n + aloga)

Space complexity: O(n)

C++

class Solution {

public:

vector<string> reorderLogFiles(vector<string>& logs) {

auto alpha_end = std::stable_partition(begin(logs), end(logs),

[](const string& log){ return isalpha(log.back()); });

std::sort(begin(logs), alpha_end, [](const string& a, const string& b){

return a.substr(a.find(' ')) < b.substr(b.find(' '));

});

return logs;

}

};

花花酱 LeetCode 648. Replace Words

By zxi on November 8, 2018

Problem

https://leetcode.com/problems/replace-words/description/

In English, we have a concept called root, which can be followed by some other words to form another longer word – let’s call this word successor. For example, the root an, followed by other, which can form another word another.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.

You need to output the sentence after the replacement.

Example 1:

Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Note:

The input will only have lower-case letters.
1 <= dict words number <= 1000
1 <= sentence words number <= 1000
1 <= root length <= 100
1 <= sentence words length <= 1000

Solution 1: HashTable

Time complexity: O(sum(w^2))

Space complexity: O(sum(l))

// Author: Huahua, Running time: 84 ms

class Solution {

public:

string replaceWords(vector<string>& dict, string sentence) {

unordered_set<string> d(begin(dict), end(dict));

sentence.push_back(' ');

string output;

string word;

bool found = false;

for (char c : sentence) {

if (c == ' ') {

if (!output.empty()) output += ' ';

output += word;

word = "";

found = false;

continue;

}

if (found) continue;

word += c;

if (d.count(word)) {

found = true;

}

return output;

}

};

Solution2: Trie

Time complexity: O(sum(l) + n)

Space complexity: O(sum(l) * 26)

// Author: Huahua, running time: 48 ms

class TrieNode {

public:

TrieNode(): children(26), is_word(false) {}

~TrieNode() {

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

if (children[i]) {

delete children[i];

children[i] = nullptr;

}

vector<TrieNode*> children;

bool is_word;

};

class Solution {

public:

string replaceWords(vector<string>& dict, string sentence) {

TrieNode root;

for (const string& word : dict) {

TrieNode* cur = &root;

for (char c : word) {

if (!cur->children[c - 'a']) cur->children[c - 'a'] = new TrieNode();

cur = cur->children[c - 'a'];

}

cur->is_word = true;

}

string ans;

stringstream ss(sentence);

string word;

while (ss >> word) {

TrieNode* cur = &root;

bool found = false;

int len = 0;

for (char c : word) {

cur = cur->children[c - 'a'];

if (!cur) break;

++len;

if (cur->is_word) {

found = true;

break;

}

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

ans += found ? word.substr(0, len) : word;

}

return ans;

}

};

花花酱 LeetCode 929. Unique Email Addresses

By zxi on October 28, 2018

Every email consists of a local name and a domain name, separated by the @ sign.

For example, in alice@leetcode.com, alice is the local name, and leetcode.com is the domain name.

Besides lowercase letters, these emails may contain '.'s or '+'s.

If you add periods ('.') between some characters in the local name part of an email address, mail sent there will be forwarded to the same address without dots in the local name. For example, "alice.z@leetcode.com" and "alicez@leetcode.com" forward to the same email address. (Note that this rule does not apply for domain names.)

If you add a plus ('+') in the local name, everything after the first plus sign will be ignored. This allows certain emails to be filtered, for example m.y+name@email.com will be forwarded to my@email.com. (Again, this rule does not apply for domain names.)

It is possible to use both of these rules at the same time.

Given a list of emails, we send one email to each address in the list. How many different addresses actually receive mails?

Example 1:

Input: ["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"]
Output: 2
Explanation: "testemail@leetcode.com" and "testemail@lee.tcode.com" actually receive mails

Note:

1 <= emails[i].length <= 100
1 <= emails.length <= 100
Each emails[i] contains exactly one '@' character.

Solution:

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

C++

// Author: Huahua, 24 ms

class Solution {

public:

int numUniqueEmails(vector<string>& emails) {

unordered_set<string> s;

for (const string& email : emails) {

string e;

bool at = false;

bool plus = false;

for (char c : email) {

if (c == '.') {

if (!at) continue;

} else if (c == '@') {

at = true;

} else if (c == '+') {

if (!at) {

plus = true;

continue;

}

if (!at && plus) continue;

e += c;

}

s.insert(std::move(e));

}

return s.size();

}

};

花花酱 LeetCode 927. Three Equal Parts

By zxi on October 20, 2018

Problem

Given an array A of 0s and 1s, divide the array into 3 non-empty parts such that all of these parts represent the same binary value.

If it is possible, return any [i, j] with i+1 < j, such that:

A[0], A[1], ..., A[i] is the first part;
A[i+1], A[i+2], ..., A[j-1] is the second part, and
A[j], A[j+1], ..., A[A.length - 1] is the third part.
All three parts have equal binary value.

If it is not possible, return [-1, -1].

Note that the entire part is used when considering what binary value it represents. For example, [1,1,0] represents 6 in decimal, not 3. Also, leading zeros are allowed, so [0,1,1] and [1,1] represent the same value.

Example 1:

Input: [1,0,1,0,1]
Output: [0,3]

Example 2:

Input: [1,1,0,1,1]
Output: [-1,-1]

Note:

3 <= A.length <= 30000
A[i] == 0 or A[i] == 1

Solution:

each part should have the same number of 1 s.

Find the suffix (without leading os) of the last part which should have 1/3 of the total ones.

Time complexity: O(n^2) in theory but close to O(n) in practice

Space complexity: O(n)

C++

// Author: Huahua, 44 ms

class Solution {

public:

vector<int> threeEqualParts(vector<int>& A) {

string s(begin(A), end(A));

int ones = accumulate(begin(A), end(A), 0);

if (ones % 3 != 0) return {-1, -1};

if (ones == 0) return {0, A.size() - 1};

ones /= 3;

int right = A.size() - 1;

while (ones) if (A[right--]) --ones;

string suffix(begin(s) + right + 1, end(s));

size_t l = suffix.length();

size_t left = s.find(suffix);

if (left == std::string::npos) return {-1, -1};

size_t mid = s.find(suffix, left + l);

if (mid == std::string::npos

|| mid + 2 * l > s.length()) return {-1, -1};

return {left + l - 1, mid + l};

}

};

花花酱 LeetCode 917. Reverse Only Letters

By zxi on October 6, 2018

Problem

Given a string S, return the “reversed” string where all characters that are not a letter stay in the same place, and all letters reverse their positions.

Example 1:

Input: "ab-cd"
Output: "dc-ba"

Example 2:

Input: "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"

Example 3:

Input: "Test1ng-Leet=code-Q!"
Output: "Qedo1ct-eeLg=ntse-T!"

Note:

S.length <= 100
33 <= S[i].ASCIIcode <= 122
S doesn’t contain \ or "

Solution: Two Pointers

Time complexity: O(n)

Space complexity: O(1) – in place

C++/index

// Author: Huahua

class Solution {

public:

string reverseOnlyLetters(string S) {

int i = 0;

int j = S.length() - 1;

while (i < j) {

if (isalpha(S[i]) && isalpha(S[j])) {

swap(S[i++], S[j--]);

} else {

if (!isalpha(S[i])) ++i;

if (!isalpha(S[j])) --j;

}

return S;

}

};

C++/iter

// Author: Huahua

class Solution {

public:

string reverseOnlyLetters(string S) {

auto it1 = begin(S);

auto it2 = prev(end(S));

while (it1 < it2) {

if (isalpha(*it1) && isalpha(*it2)) {

swap(*it1++, *it2--);

} else {

if (!isalpha(*it1)) ++it1;

if (!isalpha(*it2)) --it2;

}

return S;

}

};