Posts tagged as “string”

花花酱 LeetCode 953. Verifying an Alien Dictionary

By zxi on December 9, 2018

Problem

In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.

Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographicaly in this alien language.

Example 1:

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.

Example 2:

Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output: false
Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.

Example 3:

Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output: false
Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info).

Note:

1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
All characters in words[i] and order are english lowercase letters.

Solution: Hashtable

Time complexity: O(sum(len(words[i])))

Space complexity: O(26)

C++

// Author: Huahua, 8 ms

class Solution {

public:

bool isAlienSorted(vector<string>& words, string order) {

vector<char> m(26);

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

m[order[i] - 'a'] = 'a' + i;

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

for (int j = 0; j < words[i].length(); ++j)

words[i][j] = m[words[i][j] - 'a'];

if (i > 0 && words[i] < words[i - 1]) return false;

}

return true;

}

};

花花酱 LeetCode 944. Delete Columns to Make Sorted

By zxi on November 18, 2018

Problem

We are given an array A of N lowercase letter strings, all of the same length.

Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.

For example, if we have a string "abcdef" and deletion indices {0, 2, 3}, then the final string after deletion is "bef".

Suppose we chose a set of deletion indices D such that after deletions, each remaining column in A is in non-decreasing sorted order.

Formally, the c-th column is [A[0][c], A[1][c], ..., A[A.length-1][c]]

Return the minimum possible value of D.length.

Example 1:

Input: ["cba","daf","ghi"]
Output: 1

Example 2:

Input: ["a","b"]
Output: 0

Example 3:

Input: ["zyx","wvu","tsr"]
Output: 3

Note:

1 <= A.length <= 100
1 <= A[i].length <= 1000

Solution: Simulation

Check descending case column by column.

Time complexity: O(NL)

Space complexity: O(1)

C++

// Author: Huahua, 64 ms

class Solution {

public:

int minDeletionSize(vector<string>& A) {

int ans = 0;

for (int c = 0; c < A[0].size(); ++c)

for (int r = 1; r < A.size(); ++r) {

if (A[r][c] < A[r - 1][c]) {

++ans;

break;

}

return ans;

}

};

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

}

};