花花酱 LeetCode 966. Vowel Spellchecker

By zxi on December 30, 2018

Problem

Given a wordlist, we want to implement a spellchecker that converts a query word into a correct word.

For a given query word, the spell checker handles two categories of spelling mistakes:

Capitalization: If the query matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the case in the wordlist.
- Example: wordlist = ["yellow"], query = "YellOw": correct = "yellow"
- Example: wordlist = ["Yellow"], query = "yellow": correct = "Yellow"
- Example: wordlist = ["yellow"], query = "yellow": correct = "yellow"
Vowel Errors: If after replacing the vowels (‘a’, ‘e’, ‘i’, ‘o’, ‘u’) of the query word with any vowel individually, it matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the match in the wordlist.
- Example: wordlist = ["YellOw"], query = "yollow": correct = "YellOw"
- Example: wordlist = ["YellOw"], query = "yeellow": correct = "" (no match)
- Example: wordlist = ["YellOw"], query = "yllw": correct = "" (no match)

In addition, the spell checker operates under the following precedence rules:

When the query exactly matches a word in the wordlist (case-sensitive), you should return the same word back.
When the query matches a word up to capitlization, you should return the first such match in the wordlist.
When the query matches a word up to vowel errors, you should return the first such match in the wordlist.
If the query has no matches in the wordlist, you should return the empty string.

Given some queries, return a list of words answer, where answer[i] is the correct word for query = queries[i].

Example 1:

Input: wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]
Output: ["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]

Note:

1 <= wordlist.length <= 5000
1 <= queries.length <= 5000
1 <= wordlist[i].length <= 7
1 <= queries[i].length <= 7
All strings in wordlist and queries consist only of english letters.

Solution: HashTable

Using 3 hashtables: original words, lower cases, lower cases with vowels replaced to “*”

Time complexity: O(|W|+|Q|)
Space complexity: O(|W|)

C++

class Solution {

public:

vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {

vector<string> ans;

unordered_map<string, string> m_org;

unordered_map<string, string> m_low;

unordered_map<string, string> m_vow;

for (const string& w : wordlist) {

// Original word

m_org[w] = w;

// Case-insensitive

string l = toLower(w);

if (!m_low.count(l)) m_low[l] = w;

// Vowel-insensitive

string o = replaceVowels(l);

if (!m_vow.count(o)) m_vow[o] = w;

}

for (const string& q : queries) {

if (m_org.count(q)) {

ans.push_back(q);

continue;

}

string l = toLower(q);

if (m_low.count(l)) {

ans.push_back(m_low[l]);

continue;

}

string o = replaceVowels(l);

if (m_vow.count(o)) {

ans.push_back(m_vow[o]);

continue;

}

ans.push_back("");

}

return ans;

}

private:

string toLower(const string& s) {

string l(s);

std::transform(begin(s), end(s), begin(l), ::tolower);

return l;

}

string replaceVowels(const string& s) {

string o(s);

for (char& c : o)

if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')

c = '*';

return o;

}

};

Python3

class Solution:

def spellchecker(self, wordlist, queries):

org = dict()

low = dict()

vow = dict()

for w in wordlist:

org[w] = w

l = w.lower()

if l not in low: low[l] = w

v = re.sub(r'[aeiou]', '*', l)

if v not in vow: vow[v] = w

ans = []

for q in queries:

if q in org:

ans.append(q)

continue

l = q.lower()

if l in low:

ans.append(low[l])

continue

v = re.sub(r'[aeiou]', '*', l)

if v in vow:

ans.append(vow[v])

continue

ans.append("")

return ans

花花酱 LeetCode 965. Univalued Binary Tree

By zxi on December 30, 2018

Problem

A binary tree is univalued if every node in the tree has the same value.

Return true if and only if the given tree is univalued.

Example 1:

Input: [1,1,1,1,1,null,1]
Output: true

Example 2:

Input: [2,2,2,5,2]
Output: false

Note:

The number of nodes in the given tree will be in the range [1, 100].
Each node’s value will be an integer in the range [0, 99].

Solution: Recursion

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

C++

// Author: Huahua, running time: 0 ms

class Solution {

public:

bool isUnivalTree(TreeNode* root) {

if (!root) return true;

if (root->left && root->val != root->left->val) return false;

if (root->right && root->val != root->right->val) return false;

return isUnivalTree(root->left) && isUnivalTree(root->right);

}

};

Python3

# Author: Huahua, running time: 68 ms

class Solution:

def isUnivalTree(self, root):

if not root: return True

if root.left and root.left.val != root.val: return False

if root.right and root.right.val != root.val: return False

return self.isUnivalTree(root.left) and self.isUnivalTree(root.right)

花花酱 LeetCode 964. Least Operators to Express Number

By zxi on December 28, 2018

Given a single positive integer x, we will write an expression of the form x (op1) x (op2) x (op3) x ... where each operator op1, op2, etc. is either addition, subtraction, multiplication, or division (+, -, *, or /). For example, with x = 3, we might write 3 * 3 / 3 + 3 - 3 which is a value of 3.

When writing such an expression, we adhere to the following conventions:

The division operator (/) returns rational numbers.
There are no parentheses placed anywhere.
We use the usual order of operations: multiplication and division happens before addition and subtraction.
It’s not allowed to use the unary negation operator (-). For example, “x - x” is a valid expression as it only uses subtraction, but “-x + x” is not because it uses negation.

We would like to write an expression with the least number of operators such that the expression equals the given target. Return the least number of operators used.

Example 1:

Input: x = 3, target = 19 
Output: 5 
Explanation: 3 * 3 + 3 * 3 + 3 / 3.  The expression contains 5 operations.

Example 2:

Input: x = 5, target = 501 
Output: 8 
Explanation: 5 * 5 * 5 * 5 - 5 * 5 * 5 + 5 / 5.  The expression contains 8 operations.

Example 3:

Input: x = 100, target = 100000000 
Output: 3 
Explanation: 100 * 100 * 100 * 100.  The expression contains 3 operations.

Note:

2 <= x <= 100
1 <= target <= 2 * 10^8

Solution: Dijkstra

Find the shortest path from target to 0 using ops.

Time complexity: O(nlogn)
Space complexity: O(nlogn)
n = x * log(t) / log(x)

C++/set

class Solution {

public:

int leastOpsExpressTarget(int x, int target) {

set<pair<int, int>> q; // # x -> number

unordered_set<int> s;

q.emplace(0, target);

while (!q.empty()) {

const auto it = begin(q);

const int c = it->first;

const int t = it->second;

q.erase(it);

if (t == 0) return c - 1;

if (s.count(t)) continue;

s.insert(t);

int n = log(t) / log(x);

int l = t - pow(x, n);

q.emplace(c + (n == 0 ? 2 : n), l);

int r = pow(x, n + 1) - t;

q.emplace(c + n + 1, r);

}

return -1;

}

};

C++/heap

class Solution {

public:

int leastOpsExpressTarget(int x, int target) {

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

unordered_set<int> s;

q.emplace(0, target);

while (!q.empty()) {

const int c = q.top().first;

const int t = q.top().second;

q.pop();

if (t == 0) return c - 1;

if (s.count(t)) continue;

s.insert(t);

int n = log(t) / log(x);

int l = t - pow(x, n);

q.emplace(c + (n == 0 ? 2 : n), l);

int r = pow(x, n + 1) - t;

q.emplace(c + n + 1, r);

}

return -1;

}

};

Solution 2: DFS + Memoization

Time complexity: O(x * log(t)/log(x))
Space complexity: O(x * log(t)/log(x))

C++

// Author: Huahua, running time: 8 ms

class Solution {

public:

int leastOpsExpressTarget(int x, int target) {

return dp(x, target);

}

private:

unordered_map<int, int> m_;

int dp(int x, int t) {

if (t == 0) return 0;

if (t < x) return min(2 * t - 1, 2 * (x - t));

if (m_.count(t)) return m_.at(t);

int k = log(t) / log(x);

long p = pow(x, k);

if (t == p) return m_[t] = k - 1;

int ans = dp(x, t - p) + k; // t - p < t

long left = p * x - t;

if (left < t) // only rely on smaller sub-problems

ans = min(ans, dp(x, left) + k + 1);

return m_[t] = ans;

}

};

花花酱 LeetCode 963. Minimum Area Rectangle II

By zxi on December 26, 2018

Given a set of points in the xy-plane, determine the minimum area of any rectangle formed from these points, with sides not necessarily parallel to the x and y axes.

If there isn’t any rectangle, return 0.

Example 1:

Input: [[1,2],[2,1],[1,0],[0,1]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [1,2],[2,1],[1,0],[0,1], with an area of 2.

Example 2:

Input: [[0,1],[2,1],[1,1],[1,0],[2,0]]
Output: 1.00000
Explanation: The minimum area rectangle occurs at [1,0],[1,1],[2,1],[2,0], with an area of 1.

Example 3:

Input: [[0,3],[1,2],[3,1],[1,3],[2,1]]
Output: 0
Explanation: There is no possible rectangle to form from these points.

Example 4:

Input: [[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [2,1],[2,3],[3,3],[3,1], with an area of 2.

Note:

1 <= points.length <= 50
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
All points are distinct.
Answers within 10^-5 of the actual value will be accepted as correct.

Solution: HashTable

Iterate all possible triangles and check the opposite points that creating a quadrilateral.

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

C++

class Solution {

public:

double minAreaFreeRect(vector<vector<int>>& points) {

constexpr double INF_AREA = 1e100;

const auto n = points.size();

unordered_set<int> s;

for (const auto& p : points)

s.insert(p[0] << 16 | p[1]);

double min_area = INF_AREA;

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

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

if (i == j) continue;

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

if (i == k || j == k) continue;

const auto& p1 = points[i];

const auto& p2 = points[j];

const auto& p3 = points[k];

int dot = (p2[0] - p1[0]) * (p3[0] - p1[0]) +

(p2[1] - p1[1]) * (p3[1] - p1[1]);

if (dot != 0) continue;

int p4_x = p2[0] + p3[0] - p1[0];

int p4_y = p2[1] + p3[1] - p1[1];

if (!s.count(p4_x << 16 | p4_y)) continue;

double a = pow(p2[0] - p1[0], 2) + pow(p2[1] - p1[1], 2);

double b = pow(p3[0] - p1[0], 2) + pow(p3[1] - p1[1], 2);

double area = a * b;

min_area = min(min_area, area);

}

return min_area < INF_AREA ? sqrt(min_area) : 0;

}

};

花花酱 LeetCode 962. Maximum Width Ramp

By zxi on December 25, 2018

Given an array A of integers, a ramp is a tuple (i, j) for which i < j and A[i] <= A[j]. The width of such a ramp is j - i.

Find the maximum width of a ramp in A. If one doesn’t exist, return 0.

Example 1:

Input: [6,0,8,2,1,5] 
Output: 4 
Explanation:  The maximum width ramp is achieved at (i, j) = (1, 5): A[1] = 0 and A[5] = 5.

Example 2:

Input: [9,8,1,0,1,9,4,0,4,1] 
Output: 7 
Explanation:  The maximum width ramp is achieved at (i, j) = (2, 9): A[2] = 1 and A[9] = 1.

Note:

2 <= A.length <= 50000
0 <= A[i] <= 50000

Solution: Stack

Using a stack to store start candidates’ (decreasing order) index
Scan from right to left, compare the current number with the one on the top of the stack, pop if greater.

e.g.
A = [6,0,8,2,1,5]
stack = [0, 1] => [6, 0]
cur: A[5] = 5, stack.top = A[1] = 0, ramp = 5, stack.pop()
cur: A[4] = 1, stack.top = A[0] = 6
cur: A[3] = 2, stack.top = A[0] = 6
cur: A[2] = 8, stack.top = A[0] = 6, ramp = 2, stack.pop()
stack.isEmpty() => END

C++

// Author: Huahua, running time: 44 ms

class Solution {

public:

int maxWidthRamp(vector<int>& A) {

stack<int> s;

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

if (s.empty() || A[i] < A[s.top()])

s.push(i);

int ans = 0;

for (int i = A.size() - 1; i >= 0; --i)

while (!s.empty() && A[i] >= A[s.top()]) {

ans = max(ans, i - s.top());

s.pop();

}

return ans;

}

};

Python3

# Author: Huahua, running time: 92 ms

class Solution:

def maxWidthRamp(self, A):

s = []

for i in range(len(A)):

if not s or A[i] < A[s[-1]]: s.append(i)

ans = 0

for i in range(len(A) - 1, -1, -1):

while s and A[i] >= A[s[-1]]:

ans = max(ans, i - s.pop())

return ans

Huahua's Tech Road

花花酱 LeetCode 966. Vowel Spellchecker

Problem

Solution: HashTable

C++

Python3

花花酱 LeetCode 965. Univalued Binary Tree

Problem

Solution: Recursion

C++

Python3

Related Problems

花花酱 LeetCode 964. Least Operators to Express Number

Solution: Dijkstra

C++/set

C++/heap

Solution 2: DFS + Memoization

C++

花花酱 LeetCode 963. Minimum Area Rectangle II

Solution: HashTable

C++

花花酱 LeetCode 962. Maximum Width Ramp

Solution: Stack

C++

Python3