花花酱 LeetCode 17. Letter Combinations of a Phone Number

By zxi on December 29, 2017

题目大意：给你一串电话号码，输出可以由这串电话号码打出的所有字符串。

Problem:

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

1 2	Input:Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Solution 1: DFS

C++

// Author: Huahua

// Runtime: 0 ms

class Solution {

public:

vector<string> letterCombinations(string digits) {

if (digits.empty()) return {};

vector<vector<char>> d(10);

d[0] = {' '};

d[1] = {};

d[2] = {'a','b','c'};

d[3] = {'d','e','f'};

d[4] = {'g','h','i'};

d[5] = {'j','k','l'};

d[6] = {'m','n','o'};

d[7] = {'p','q','r','s'};

d[8] = {'t','u','v'};

d[9] = {'w','x','y','z'};

string cur;

vector<string> ans;

dfs(digits, d, 0, cur, ans);

return ans;

}

private:

void dfs(const string& digits,

const vector<vector<char>>& d,

int l, string& cur, vector<string>& ans) {

if (l == digits.length()) {

ans.push_back(cur);

return;

}

for (const char c : d[digits[l] - '0']) {

cur.push_back(c);

dfs(digits, d, l + 1, cur, ans);

cur.pop_back();

}

};

Java

// Author: Huahua

// Running time: 3 ms

class Solution {

public List<String> letterCombinations(String digits) {

String[] d = new String[]{" ",

"",

"abc",

"def",

"ghi",

"jkl",

"mno",

"pqrs",

"tuv",

"wxyz"};

char[] cur = new char[digits.length()];

List<String> ans = new ArrayList<>();

dfs(digits, d, 0, cur, ans);

return ans;

}

private void dfs(String digits, String[] d,

int l, char[] cur, List<String> ans) {

if (l == digits.length()) {

if (l > 0) ans.add(new String(cur));

return;

}

String s = d[Character.getNumericValue(digits.charAt(l))];

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

cur[l] = s.charAt(i);

dfs(digits, d, l + 1, cur, ans);

}

Python3

"""

Author: Huahua

Running time: 60 ms

"""

class Solution:

def letterCombinations(self, digits):

def dfs(digits, d, l, cur, ans):

if l == len(digits):

if l > 0: ans.append("".join(cur))

return

for c in d[ord(digits[l]) - ord('0')]:

cur[l] = c

dfs(digits, d, l + 1, cur, ans)

d = [" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv","wxyz"]

cur = [' ' for _ in range(len(digits))]

ans = []

dfs(digits, d, 0, cur, ans)

return ans

Solution 2: BFS

C++

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

vector<string> letterCombinations(string digits) {

if (digits.empty()) return {};

vector<vector<char>> d(10);

d[0] = {' '};

d[1] = {};

d[2] = {'a','b','c'};

d[3] = {'d','e','f'};

d[4] = {'g','h','i'};

d[5] = {'j','k','l'};

d[6] = {'m','n','o'};

d[7] = {'p','q','r','s'};

d[8] = {'t','u','v'};

d[9] = {'w','x','y','z'};

vector<string> ans{""};

for (char digit : digits) {

vector<string> tmp;

for (const string& s : ans)

for (char c : d[digit - '0'])

tmp.push_back(s + c);

ans.swap(tmp);

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 4 ms

class Solution {

public List<String> letterCombinations(String digits) {

if (digits.length() == 0) return new ArrayList<String>();

String[] d = new String[]{" ",

"",

"abc",

"def",

"ghi",

"jkl",

"mno",

"pqrs",

"tuv",

"wxyz"};

List<String> ans = new ArrayList<>();

ans.add("");

for (char digit : digits.toCharArray()) {

List<String> tmp = new ArrayList<>();

for (String t : ans) {

String s = d[Character.getNumericValue(digit)];

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

tmp.add(t + s.charAt(i));

}

ans = tmp;

}

return ans;

}

Python

"""

Author: Huahua

Running time: 61 ms

"""

class Solution:

def letterCombinations(self, digits):

if not digits: return []

d = [" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv","wxyz"]

ans = [""]

for digit in digits:

tmp = []

for s in ans:

for c in d[ord(digit) - ord('0')]:

tmp.append(s + c)

ans = tmp

return ans

花花酱 LeetCode Input Size V.S. Time Complexity SP2

By zxi on December 28, 2017

本期节目介绍了输入数据规模和时间复杂度上限的关系，可以通过数据规模推算使用算法的类型。

< 10: O(n!) permutation
< 15: O(2^n) combination
< 50: O(n^4) DP
< 200: O(n^3) DP, all pairs shortest path
< 1,000: O(n^2) DP, all pairs, dense graph
< 1,000,000: O(nlogn), sorting-based (greedy), heap, divide & conquer
< 1,000,000: O(n), DP, graph traversal / topological sorting (V+E), tree traversal
< INT_MAX: O(sqrt(n)), prime, square sum
< INT_MAX: O(logn), binary search
< INT_MAX: O(1) Math

花花酱 LeetCode 752. Open the Lock

By zxi on December 25, 2017

Problem:

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Example 1:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"

Output: 6

Explanation:

A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".

Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,

because the wheels of the lock become stuck after the display becomes the dead end "0102".

Example 2:

Input: deadends = ["8888"], target = "0009"

Output: 1

Explanation:

We can turn the last wheel in reverse to move from "0000" -> "0009".

Example 3:

Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"

Output: -1

Explanation:

We can't reach the target without getting stuck.

Example 4:

1 2	Input: deadends = ["0000"], target = "8888" Output: -1

Note:

The length of deadends will be in the range [1, 500].
target will not be in the list deadends.
Every string in deadends and the string target will be a string of 4 digits from the 10,000 possibilities '0000' to '9999'.

题目大意：

给你一个4位密码锁，0可以转到1和9，1可以转到0和2，。。。，9可以转到0和8。

另外给你一些死锁的密码，比如1234，一但转到任何一个死锁的密码，锁就无法再转动了。

给你一个目标密码，问你最少要转多少次才能从0000转到目标密码。

Solution:

C++

// Author: Huahua

// Runtime: 133 ms

class Solution {

public:

int openLock(vector<string>& deadends, string target) {

const string start = "0000";

unordered_set<string> dead(deadends.begin(), deadends.end());

if (dead.count(start)) return -1;

if (start == target) return 0;

queue<string> q;

unordered_set<string> visited{start};

int steps = 0;

q.push(start);

while (!q.empty()) {

++steps;

const int size = q.size();

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

const string curr = q.front();

q.pop();

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

for (int j = -1; j <= 1; j += 2) {

string next = curr;

next[i] = (next[i] - '0' + j + 10) % 10 + '0';

if (next == target) return steps;

if (dead.count(next) || visited.count(next)) continue;

q.push(next);

visited.insert(next);

}

return -1;

}

};

C++ / Bidirectional BFS

// Author: Huahua

// Runtime: 32 ms

class Solution {

public:

int openLock(vector<string>& deadends, string target) {

const string start = "0000";

unordered_set<string> dead(deadends.begin(), deadends.end());

if (dead.count(start)) return -1;

if (target == start) return 0;

queue<string> q1;

queue<string> q2;

unordered_set<string> v1{start};

unordered_set<string> v2{target};

int s1 = 0;

int s2 = 0;

q1.push(start);

q2.push(target);

while (!q1.empty() && !q2.empty()) {

if (!q1.empty()) ++s1;

const int size = q1.size();

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

const string curr = q1.front();

q1.pop();

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

for (int j = -1; j <= 1; j += 2) {

string next = curr;

next[i] = (next[i] - '0' + j + 10) % 10 + '0';

if (v2.count(next)) return s1 + s2;

if (dead.count(next) || v1.count(next)) continue;

q1.push(next);

v1.insert(next);

}

swap(q1, q2);

swap(v1, v2);

swap(s1, s2);

}

return -1;

}

};

C++ / Bidirectional BFS / int state / Array

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

int openLock(vector<string>& deadends, string target) {

constexpr int kMaxN = 10000;

const vector<int> bases{1, 10, 100, 1000};

const int start = 0;

const int goal = stoi(target);

queue<int> q1;

queue<int> q2;

vector<int> v1(kMaxN, 0);

vector<int> v2(kMaxN, 0);

for (const string& deadend : deadends)

v1[stoi(deadend)] = v2[stoi(deadend)] = -1;

if (v1[start] == -1) return -1;

if (start == goal) return 0;

v1[start] = 1;

v2[goal] = 1;

int s1 = 0;

int s2 = 0;

q1.push(start);

q2.push(goal);

while (!q1.empty() && !q2.empty()) {

if (!q1.empty()) ++s1;

const int size = q1.size();

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

const int curr = q1.front();

q1.pop();

for (int i = 0; i < 4; ++i) {

int r = (curr / bases[i]) % 10;

for (int j = -1; j <= 1; j += 2) {

const int next = curr + ((r + j + 10) % 10 - r) * bases[i];

if (v2[next] == 1) return s1 + s2;

if (v1[next]) continue;

q1.push(next);

v1[next] = 1;

}

swap(q1, q2);

swap(v1, v2);

swap(s1, s2);

}

return -1;

}

};

Java

// Author: Huahua

// Runtime: 132 ms

class Solution {

public int openLock(String[] deadends, String target) {

String start = "0000";

Set<String> dead = new HashSet();

for (String d: deadends) dead.add(d);

if (dead.contains(start)) return -1;

Queue<String> queue = new LinkedList();

queue.offer(start);

Set<String> visited = new HashSet();

visited.add(start);

int steps = 0;

while (!queue.isEmpty()) {

++steps;

int size = queue.size();

for (int s = 0; s < size; ++s) {

String node = queue.poll();

for (int i = 0; i < 4; ++i) {

for (int j = -1; j <= 1; j += 2) {

char[] chars = node.toCharArray();

chars[i] = (char)(((chars[i] - '0') + j + 10) % 10 + '0');

String next = new String(chars);

if (next.equals(target)) return steps;

if (dead.contains(next) || visited.contains(next))

continue;

visited.add(next);

queue.offer(next);

}

return -1;

}

Python

"""

Author: Huahua

Runtime: 955 ms

"""

class Solution:

def openLock(self, deadends, target):

from collections import deque

deads = set(deadends)

start = '0000'

if start in deads: return -1

q = deque([(start, 0)])

visited = set(start)

while q:

node, step = q.popleft()

for i in range(0, 4):

for j in [-1, 1]:

nxt = node[:i] + str((int(node[i]) + j + 10) % 10) + node[i+1:]

if nxt == target: return step + 1

if nxt in deads or nxt in visited: continue

q.append((nxt, step + 1))

visited.add(nxt)

return -1

Python / Int state

"""

Author: Huahua

Runtime: 568 ms

"""

class Solution:

def openLock(self, deadends, target):

from collections import deque

bases = [1, 10, 100, 1000]

deads = set(int(x) for x in deadends)

start, goal = int('0000'), int(target)

if start in deads: return -1

if start == goal: return 0

q = deque([(start, 0)])

visited = set([start])

while q:

node, step = q.popleft()

for i in range(0, 4):

r = (node // bases[i]) % 10

for j in [-1, 1]:

nxt = node + ((r + j + 10) % 10 - r) * bases[i]

if nxt == goal: return step + 1

if nxt in deads or nxt in visited: continue

q.append((nxt, step + 1))

visited.add(nxt)

return -1

花花酱 LeetCode 121. Best Time to Buy and Sell Stock

By zxi on December 22, 2017

题目大意: 给你一只股票每天的价格，如果只能做一次交易（一次买进一次卖出）问你最多能赚多少钱。

Problem:

Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]

Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]

Output: 0

In this case, no transaction is done, i.e. max profit = 0.

Idea:

Solution 1:

C++

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

int maxProfit(vector<int>& prices) {

const int n = prices.size();

if (n < 1) return 0;

vector<int> min_prices(n);

vector<int> max_profit(n);

min_prices[0] = prices[0];

max_profit[0] = 0;

for (int i = 1; i < n; ++i) {

min_prices[i] = min(min_prices[i - 1],

prices[i]);

max_profit[i] = max(max_profit[i - 1],

prices[i] - min_prices[i - 1]);

}

return max_profit[n - 1];

}

};

C++ / reduce to maximum subarray

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

int maxProfit(vector<int>& prices) {

int n = prices.size();

if (n < 2) return 0;

vector<int> gains(n - 1, 0);

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

gains[i - 1] = prices[i] - prices[i - 1];

return max(0, maxSubArray(gains));

}

private:

// From LC 53. Maximum Subarray

int maxSubArray(vector<int>& nums) {

vector<int> f(nums.size());

f[0] = nums[0];

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

f[i] = max(f[i - 1] + nums[i], nums[i]);

return *std::max_element(f.begin(), f.end());

}

};

Related Problems:

花花酱 LeetCode 309. Best Time to Buy and Sell Stock with Cooldown

花花酱 LeetCode 301. Remove Invalid Parentheses

By zxi on December 21, 2017

Problem:

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:

"()())()" -> ["()()()", "(())()"]

"(a)())()" -> ["(a)()()", "(a())()"]

")(" -> [""]

题目大意：给你一个字符串，由”(” “)”和其他字符构成。让你删除数量最少的括号使得表达式合法（括号都匹配）。输出所有的合法表达式。

Idea:

Solution: DFS

C++

// Author: Huahua

// Runtime: 0 ms

class Solution {

public:

vector<string> removeInvalidParentheses(const string& s) {

int l = 0;

int r = 0;

for (const char ch : s) {

l += (ch == '(');

if (l == 0)

r += (ch == ')');

else

l -= (ch == ')');

}

vector<string> ans;

dfs(s, 0, l, r, ans);

return ans;

}

private:

bool isValid(const string& s) {

int count = 0;

for (const char ch : s) {

if (ch == '(') ++count;

if (ch == ')') --count;

if (count < 0) return false;

}

return count == 0;

}

// l/r: number of left/right parentheses to remove.

void dfs(const string& s, int start, int l, int r, vector<string>& ans) {

// Nothing to remove.

if (l == 0 && r == 0) {

if (isValid(s)) ans.push_back(s);

return;

}

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

// We only remove the first parenthes if there are consecutive ones to avoid duplications.

if (i != start && s[i] == s[i - 1]) continue;

if (s[i] == '(' || s[i] == ')') {

string curr = s;

curr.erase(i, 1);

if (r > 0 && s[i] == ')')

dfs(curr, i, l, r - 1, ans);

else if (l > 0 && s[i] == '(')

dfs(curr, i, l - 1, r, ans);

}

};

Huahua's Tech Road

花花酱 LeetCode 17. Letter Combinations of a Phone Number

C++

Java

Python3

C++

Java

Python

花花酱 LeetCode Input Size V.S. Time Complexity SP2

花花酱 LeetCode 752. Open the Lock

花花酱 LeetCode 121. Best Time to Buy and Sell Stock

花花酱 LeetCode 301. Remove Invalid Parentheses

Solution: DFS

C++