Posts published in November 2017

花花酱 LeetCode 639. Decode Ways II

By zxi on November 18, 2017

Problem:

A message containing letters from A-Z is being encoded to numbers using the following mapping way:

'A' -> 1

'B' -> 2

...

'Z' -> 26

Beyond that, now the encoded string can also contain the character ‘*’, which can be treated as one of the numbers from 1 to 9.

Given the encoded message containing digits and the character ‘*’, return the total number of ways to decode it.

Also, since the answer may be very large, you should return the output mod 10⁹ + 7.

Example 1:

Input: "*"

Output: 9

Explanation: The encoded message can be decoded to the string:

"A", "B", "C", "D", "E", "F", "G", "H", "I".

Example 2:

1 2	Input: "1*" Output: 9 + 9 = 18

Note:

The length of the input string will fit in range [1, 10⁵].
The input string will only contain the character ‘*’ and digits ‘0’ – ‘9’.

Idea:

Time complexity: O(n)

Space complexity: O(1)

Solution:

C++

// Author: Huahua

// Runtime: 58 ms

class Solution {

public:

int numDecodings(string s) {

if (s.empty()) return 0;

// dp[-1] dp[0]

long dp[2] = {1, ways(s[0])};

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

long dp_i = ways(s[i]) * dp[1] + ways(s[i - 1], s[i]) * dp[0];

dp_i %= kMod;

dp[0] = dp[1];

dp[1] = dp_i;

}

return dp[1];

}

private:

static constexpr int kMod = 1000000007;

int ways(char c) {

if (c == '0') return 0;

if (c == '*') return 9;

return 1;

}

int ways(char c1, char c2) {

if (c1 == '*' && c2 == '*')

return 15;

if (c1 == '*') {

return (c2 >= '0' && c2 <= '6') ? 2 : 1;

} else if (c2 == '*') {

switch (c1) {

case '1': return 9;

case '2': return 6;

default: return 0;

}

} else {

int prefix = (c1 - '0') * 10 + (c2 - '0');

return prefix >= 10 && prefix <= 26;

}

};

Related Problems:

[解题报告] LeetCode 91. Decode Ways

花花酱 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 321. Create Maximum Number

By zxi on November 14, 2017

Problem:

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

Example 1:

nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]

Example 2:

nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]

Example 3:

nums1 = [3, 9]
nums2 = [8, 9]
k = 3
return [9, 8, 9]

题目大意：给你两个数字数组和k，返回从两个数组中选取k个数字能够组成的最大值。

Idea: Greedy + DP

Solution:

Time complexity: O(k * (n1+n2)^2)

Space complexity: O(n1+n2)

C++

// Author: Huahua

// Runtime: 26 ms

class Solution {

public:

vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {

vector<int> ans;

const int n1 = nums1.size();

const int n2 = nums2.size();

for (int i = max(0, k - n2); i <= min(k, n1); ++i)

ans = max(ans, maxNumber(maxNumber(nums1, i),

maxNumber(nums2, k - i)));

return ans;

}

private:

vector<int> maxNumber(const vector<int>& nums, int k) {

vector<int> ans(k);

int j = 0;

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

while (j > 0 && nums[i] > ans[j - 1]

&& nums.size() - i > k - j) --j;

if (j < k) ans[j++] = nums[i];

}

return ans;

}

vector<int> maxNumber(const vector<int>& nums1, const vector<int>& nums2) {

vector<int> ans(nums1.size() + nums2.size());

auto s1 = nums1.cbegin();

auto e1 = nums1.cend();

auto s2 = nums2.cbegin();

auto e2 = nums2.cend();

int index = 0;

while (s1 != e1 || s2 != e2)

ans[index++] =

lexicographical_compare(s1, e1, s2, e2) ? *s2++ : *s1++;

return ans;

}

};

Java

// Author: Huahua

// Runtime: 18 ms

class Solution {

public int[] maxNumber(int[] nums1, int[] nums2, int k) {

int[] best = new int[0];

for (int i = Math.max(0, k - nums2.length);

i <= Math.min(k, nums1.length); ++i)

best = max(best, 0,

maxNumber(maxNumber(nums1, i),

maxNumber(nums2, k - i)), 0);

return best;

}

private int[] maxNumber(int[] nums, int k) {

int[] ans = new int[k];

int j = 0;

for (int i = 0; i < nums.length; ++i) {

while (j > 0 && nums[i] > ans[j - 1]

&& nums.length - i > k - j) --j;

if (j < k)

ans[j++] = nums[i];

}

return ans;

}

private int[] maxNumber(int[] nums1, int[] nums2) {

int[] ans = new int[nums1.length + nums2.length];

int s1 = 0;

int s2 = 0;

int index = 0;

while (s1 != nums1.length || s2 != nums2.length)

ans[index++] = max(nums1, s1, nums2, s2) == nums1 ?

nums1[s1++] : nums2[s2++];

return ans;

}

private int[] max(int[] nums1, int s1, int[] nums2, int s2) {

for (int i = s1; i < nums1.length; ++i) {

int j = s2 + i - s1;

if (j >= nums2.length) return nums1;

if (nums1[i] < nums2[j]) return nums2;

if (nums1[i] > nums2[j]) return nums1;

}

return nums2;

}

花花酱 LeetCode 725. Split Linked List in Parts

By zxi on November 13, 2017

Problem:

Given a (singly) linked list with head node root, write a function to split the linked list into k consecutive linked list “parts”.

The length of each part should be as equal as possible: no two parts should have a size differing by more than 1. This may lead to some parts being null.

The parts should be in order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal parts occurring later.

Return a List of ListNode’s representing the linked list parts that are formed.

Examples 1->2->3->4, k = 5 // 5 equal parts [ [1], [2], [3], [4], null ]

Example 1:

Input:

root = [1, 2, 3], k = 5

Output: [[1],[2],[3],[],[]]

Explanation:

The input and each element of the output are ListNodes, not arrays.

For example, the input root has root.val = 1, root.next.val = 2, \root.next.next.val = 3, and root.next.next.next = null.

The first element output[0] has output[0].val = 1, output[0].next = null.

The last element output[4] is null, but it's string representation as a ListNode is [].

Example 2:

Input:

root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3

Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]

Explanation:

The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

Note:

The length of root will be in the range [0, 1000].
Each value of a node in the input will be an integer in the range [0, 999].
k will be an integer in the range [1, 50].

Idea:

List + Simulation

Solution:

C++

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

vector<ListNode*> splitListToParts(ListNode* root, int k) {

int len = 0;

for (ListNode* head = root; head; head = head->next) ++len;

vector<ListNode*> ans(k, nullptr);

int l = len / k;

int r = len % k;

ListNode* head = root;

ListNode* prev = nullptr;

for (int i = 0; i < k; ++i, --r) {

ans[i] = head;

for (int j = 0; j < l + (r > 0); ++j) {

prev = head;

head = head->next;

}

if (prev) prev->next = nullptr;

}

return ans;

}

};

Java

// Author: Huahua

// Runtime: 4 ms

class Solution {

public ListNode[] splitListToParts(ListNode root, int k) {

ListNode[] ans = new ListNode[k];

int len = 0;

for (ListNode head = root; head != null; head = head.next) ++len;

int l = len / k;

int r = len % k;

ListNode prev = null;

ListNode head = root;

for (int i = 0; i < k; ++i, --r) {

ans[i] = head;

int part_len = l + ((r > 0) ? 1 : 0);

for (int j = 0; j < part_len; ++j) {

prev = head;

head = head.next;

}

if (prev != null) prev.next = null;

}

return ans;

}

Python

"""

Author: Huahua

Runtime: 79 ms

"""

class Solution:

def splitListToParts(self, root, k):

total_len = 0

head = root

while head:

total_len += 1

head = head.next

ans = [None for _ in range(k)]

l, r = total_len // k, total_len % k

prev, head = None, root

for i in range(k):

ans[i] = head

for j in range(l + (1 if r > 0 else 0)):

prev, head = head, head.next

if prev: prev.next = None

r -= 1

return ans