String Archives - Page 33 of 33 - Huahua's Tech Road

花花酱 LeetCode 720. Longest Word in Dictionary

By zxi on November 16, 2017

Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order.

If there is no answer, return the empty string.

Example 1:

Input:

words = ["w","wo","wor","worl", "world"]

Output: "world"

Explanation:

The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

Example 2:

Input:

words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]

Output: "apple"

Explanation:

Both "apply" and "apple" can be built from other words in the dictionary.

However, "apple" is lexicographically smaller than "apply".

Note:

All the strings in the input will only contain lowercase letters.
The length of words will be in the range [1, 1000].
The length of words[i] will be in the range [1, 30].

Idea:

Brute force

Trie

Solution:

C++

// Author: Huahua

// Runtime: 39 ms (better than 97.85%)

class Solution {

public:

string longestWord(vector<string>& words) {

string best;

unordered_set<string> dict(words.begin(), words.end());

for (const string& word : words) {

if (word.length() < best.length()

|| (word.length() == best.length() && word > best))

continue;

string prefix;

bool valid = true;

for (int i = 0; i < word.length() - 1 && valid; ++i) {

prefix += word[i];

if (!dict.count(prefix)) valid = false;

}

if (valid) best = word;

}

return best;

}

};

// Author: Huahua

// Runtime: 46 ms

class Solution {

public:

string longestWord(vector<string>& words) {

// Sort by length DESC, if there is a tie, sort by lexcial order.

std::sort(words.begin(), words.end(),

[](const string& w1, const string& w2){

if (w1.length() != w2.length())

return w1.length() > w2.length();

return w1 < w2;

});

unordered_set<string> dict(words.begin(), words.end());

for (const string& word : words) {

string prefix;

bool valid = true;

for (int i = 0; i < word.length() - 1 && valid; ++i) {

prefix += word[i];

if (!dict.count(prefix)) valid = false;

}

if (valid) return word;

}

return "";

}

};

Trie + Sorting

// Author: Huahua

// Runtime: 49 ms

class Trie {

public:

Trie(): root_(new TrieNode()) {}

void insert(const string& word) {

TrieNode* p = root_.get();

for (const char c : word) {

if (!p->children[c - 'a'])

p->children[c - 'a'] = new TrieNode();

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

}

p->is_word = true;

}

bool hasAllPrefixes(const string& word) {

const TrieNode* p = root_.get();

for (const char c : word) {

if (!p->children[c - 'a']) return false;

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

if (!p->is_word) return false;

}

return true;

}

private:

struct TrieNode {

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

~TrieNode() {

for (auto node : children)

delete node;

}

bool is_word;

vector<TrieNode*> children;

};

std::unique_ptr<TrieNode> root_;

};

class Solution {

public:

string longestWord(vector<string>& words) {

std::sort(words.begin(), words.end(),

[](const string& w1, const string& w2){

if (w1.length() != w2.length())

return w1.length() > w2.length();

return w1 < w2;

});

Trie trie;

for (const string& word : words)

trie.insert(word);

for (const string& word : words)

if (trie.hasAllPrefixes(word)) return word;

return "";

}

};

Trie + No sorting

// Author: Huahua

// Runtime: 56 ms

class Trie {

public:

Trie(): root_(new TrieNode()) {}

void insert(const string& word) {

TrieNode* p = root_.get();

for (const char c : word) {

if (!p->children[c - 'a'])

p->children[c - 'a'] = new TrieNode();

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

}

p->is_word = true;

}

bool hasAllPrefixes(const string& word) {

const TrieNode* p = root_.get();

for (const char c : word) {

if (!p->children[c - 'a']) return false;

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

if (!p->is_word) return false;

}

return true;

}

private:

struct TrieNode {

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

~TrieNode() {

for (auto node : children)

delete node;

}

bool is_word;

vector<TrieNode*> children;

};

std::unique_ptr<TrieNode> root_;

};

class Solution {

public:

string longestWord(vector<string>& words) {

Trie trie;

for (const string& word : words)

trie.insert(word);

string best;

for (const string& word : words) {

if (word.length() < best.length()

|| (word.length() == best.length() && word > best))

continue;

if (trie.hasAllPrefixes(word))

best = word;

}

return best;

}

};

花花酱 LeetCode 726. Number of Atoms

By zxi on November 15, 2017

Problem:

Given a chemical formula (given as a string), return the count of each atom.

An atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name.

1 or more digits representing the count of that element may follow if the count is greater than 1. If the count is 1, no digits will follow. For example, H2O and H2O2 are possible, but H1O2 is impossible.

Two formulas concatenated together produce another formula. For example, H2O2He3Mg4 is also a formula.

A formula placed in parentheses, and a count (optionally added) is also a formula. For example, (H2O2) and (H2O2)3 are formulas.

Given a formula, output the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than 1), followed by the second name (in sorted order), followed by its count (if that count is more than 1), and so on.

Example 1:

Input:

formula = "H2O"

Output: "H2O"

Explanation:

The count of elements are {'H': 2, 'O': 1}.

Example 2:

Input:

formula = "Mg(OH)2"

Output: "H2MgO2"

Explanation:

The count of elements are {'H': 2, 'Mg': 1, 'O': 2}.

Example 3:

Input:

formula = "K4(ON(SO3)2)2"

Output: "K4N2O14S4"

Explanation:

The count of elements are {'K': 4, 'N': 2, 'O': 14, 'S': 4}.

Note:

All atom names consist of lowercase letters, except for the first character which is uppercase.
The length of formula will be in the range [1, 1000].
formula will only consist of letters, digits, and round parentheses, and is a valid formula as defined in the problem.

Idea:

Recursion

Time complexity: O(n)

Space complexity: O(n)

Solution:

C++

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

string countOfAtoms(const string& formula) {

int i = 0;

string ans;

for (const auto& kv : countOfAtoms(formula, i)) {

ans += kv.first;

if (kv.second > 1) ans += std::to_string(kv.second);

}

return ans;

}

private:

map<string, int> countOfAtoms(const string& formula, int& i) {

map<string, int> counts;

while (i != formula.length()) {

if (formula[i] == '(') {

const auto& tmp_counts = countOfAtoms(formula, ++i);

const int count = getCount(formula, i);

for (const auto& kv : tmp_counts)

counts[kv.first] += kv.second * count;

} else if (formula[i] == ')') {

++i;

return counts;

} else {

const string& name = getName(formula, i);

counts[name] += getCount(formula, i);

}

return counts;

}

string getName(const string& formula, int& i) {

string name;

while (isalpha(formula[i])

&& (name.empty() || islower(formula[i]))) name += formula[i++];

return name;

}

int getCount(const string& formula, int& i) {

string count_str;

while (isdigit(formula[i])) count_str += formula[i++];

return count_str.empty() ? 1 : std::stoi(count_str);

}

};

Java

// Author: Huahua

// Runtime: 13 ms

class Solution {

private int i;

public String countOfAtoms(String formula) {

StringBuilder ans = new StringBuilder();

i = 0;

Map<String, Integer> counts = countOfAtoms(formula.toCharArray());

for (String name: counts.keySet()) {

ans.append(name);

int count = counts.get(name);

if (count > 1) ans.append("" + count);

}

return ans.toString();

}

private Map<String, Integer> countOfAtoms(char[] f) {

Map<String, Integer> ans = new TreeMap<String, Integer>();

while (i != f.length) {

if (f[i] == '(') {

++i;

Map<String, Integer> tmp = countOfAtoms(f);

int count = getCount(f);

for (Map.Entry<String, Integer> entry : tmp.entrySet())

ans.put(entry.getKey(),

ans.getOrDefault(entry.getKey(), 0)

+ entry.getValue() * count);

} else if (f[i] == ')') {

++i;

return ans;

} else {

String name = getName(f);

ans.put(name, ans.getOrDefault(name, 0) + getCount(f));

}

return ans;

}

private String getName(char[] f) {

String name = "" + f[i++];

while (i < f.length && 'a' <= f[i] && f[i] <= 'z') name += f[i++];

return name;

}

private int getCount(char[] f) {

int count = 0;

while (i < f.length && '0' <= f[i] && f[i] <= '9') {

count = count * 10 + (f[i] - '0');

++i;

}

return count == 0 ? 1 : count;

}

花花酱 LeetCode 680. Valid Palindrome II

By zxi on September 17, 2017

Problem:

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

1 2	Input: "aba" Output: True

Example 2:

Input: "abca"

Output: True

Explanation: You could delete the character 'c'.

Note:

The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

Idea:

Greedy, delete the first unmatched char

Time complexity

O(n)

Solution:

// Author: Huahua

// Running time: 118 ms

class Solution {

public:

bool validPalindrome(const string& s) {

int l = -1;

int r = s.length();

while (++l < --r)

if (s[l] != s[r])

return isPalindrome(s, l+1, r)

|| isPalindrome(s, l, r-1);

return true;

}

private:

bool isPalindrome(const string& s, int l, int r) {

while (l < r)

if (s[l++] != s[r--]) return false;

return true;

}

};

Posts published in “String”

花花酱 LeetCode 720. Longest Word in Dictionary

花花酱 LeetCode 726. Number of Atoms

花花酱 LeetCode 680. Valid Palindrome II