KK's blog

LeetCode 017 Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

**Input:** digits = "23"
**Output:** ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

**Input:** digits = ""
**Output:** []

Example 3:

**Input:** digits = "2"
**Output:** ["a","b","c"]

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

题目大意：

在拨号键盘上按下了几个键，问能打出来的字符串的所有组合是多少。。

递归法解题思路：

DFS的典型题目。

与Java的区别：

1. 直接用Str作为临时结果，不需要用char array，因为str可以含有array的性质

注意事项：

1. 输入值为空的情况
2. 终止条件记得return
3. 用常量

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

DIGIT2CHAR = {
    '0': '',
    '1': '',
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz',
}

class Solution(TestCases):

	# filling dfs (type 3) LeetCode 017 Letter Combinations of a Phone Number 
	def letterCombinations(self, digits: str) -> List[str]:
		if not digits:
			return []
		path, res = [], []
		self.dfs3(digits, 0, path, res)
		return res

	def dfs3(self, digits, start, path, res):
		if len(path) == len(digits): # len(path) == TARGET
			res.append("".join(path))
			return
		keys = DIGIT2CHAR[digits[start]]
		for letter in keys:
			path.append(letter)
			self.dfs3(digits, start + 1, path, res) # remember start + 1
			path.pop()

迭代法解题思路：

第二种方法，用迭代法，三种循环，输入数字串的每个数字，每个数字对应的字符加到当前的结果字符串列表中。

注意事项：

1. 要[‘’]而不是[]否则循环不会进行

1
2
3
4
5
6
7

def letterCombinations(self, digits: str) -> List[str]:
	if digits == '':
		return []
	result = ['']
	for d in digits:
		result = [s + c for s in result for c in DIGIT2CHAR[d]]
	return result

算法分析：

这是NP问题。时间复杂度为O(4nn)，解大小乘以path长度，空间复杂度O(1)。

LeetCode

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Input: n = 1, k = 1
Output: [[1]]

题目大意：

求大小为k的所有可能组合

解题思路：

用组合模板，先排序

解题步骤：

N/A

注意事项：

1. 引入k作为模板API中的target，k为0作为终止条件。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# char dfs (type 2 linear) Leetcode 77 Given two integers n and k, return all possible combinations of k numbers out of the range [1, n]
def combine(self, n: int, k: int) -> List[List[int]]:
	nums = [i + 1 for i in range(n)]
	path, res = [], []
	self.dfs2(nums, 0, k, [], res)
	return res

def dfs2(self, nums, start, k, path, res):
	if len(path) == k:
		res.append(list(path))
		return
	for i in range(start, len(nums)):
		path.append(nums[i])
		self.dfs2(nums, i + 1, k, path, res)
		path.pop()

算法分析：

时间复杂度为O(kCkn)，解大小乘以path长度, 空间复杂度O(n)

LeetCode 140 Word Break II

Input: s = “catsanddog“
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output: [
  "cats and dog",
  "cat sand dog"
]

Input: s = “pineapplepenapple”
wordDict = [“apple”, “pen”, “applepen”, “pine”, “pineapple”]
Output: [
  “pine apple pen apple”,
  “pineapple pen apple”,
  “pine applepen apple”
]
Explanation: Note that you are allowed to reuse a dictionary word.

Input: s = “catsandog”
wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
Output: []

题目大意：

一个字符串s，求被“字典集合”（wordDict）中的单词拼接的所有方案。

解题思路：

这是经典题。求所有可能性想到DFS，前面Lintcode 683提到可能会有重复解。所以用Cache。

Cache模板：

1. key为子问题索引st，value为子问题的解。不含path和res因为类似于Catalan(属于单边Catalan)，用子问题返回结果来组成此轮结果。f(input, st, endIndex, cache)
2. 紧跟终结条件，若在cache中，返回子问题的解。
3. 循环结束，将子问题的结果存于cache。

注意事项：

1. 终止条件返回[‘’]而不是[]，正如L017，空字符串作为初始结果。返回到上层要strip(), 因为ss可能为空
2. 子问题用f=word + f并不是f=f + word, 这样最后结果避免反转。
3. s[:i + 1]判断是否在字典中，而不是s[:i]，单词包括整个字符串。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
	word_set = set(wordDict)
	res = []
	cache = {}
	res = self.dfs(s, word_set, cache) #cat
	return res
# dfs(s) = word + dfs(s[i+1:])
def dfs(self, s, word_set, cache):
	if s == "":
		return [""]
	if s in cache:
		return cache[s]
	res = []
	for i in range(len(s)):
		if s[:i + 1] not in word_set:
			continue
		cur_list = self.dfs(s[i + 1:], word_set, cache) # i = 2, dfs("")
		for _s in cur_list: # [""]
			res.append((s[:i + 1] + " " + _s).strip()) #cat
	cache[s] = res
	return res

注意事项：

1. 将两个输入都转换成小写。
2. 复制子问题的解，不能直接在解List上编辑。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public List<String> wordBreak(String s, List<String> wordDict) {
	List<String> res = new ArrayList<>();
	if(s == null || s.isEmpty())
		return res;
	Set<String> wordDictLower = new HashSet<>();
	for(String c : wordDict)
		wordDictLower.add(c.toLowerCase());
	s = s.toLowerCase();
	Map<Integer, List<String>> cache = new HashMap<>();
	return dfs(s, wordDictLower, s.length(), cache);
}

List<String> dfs(String s, Set<String> wordDict, int st, Map<Integer, List<String>> cache) {
	if(st == 0) 
		return new ArrayList<>(Arrays.asList(""));
	if(cache.containsKey(st))
		return cache.get(st);
	List<String> result = new ArrayList<>();
	for(int i = 0; i < st; i++) {
		String word = s.substring(i, st);
		if(!wordDict.contains(word))
			continue;

		List<String> sub = dfs(s, wordDict, i, cache); 
		// copy solution for subproblem, don't edit on sub
		for(int j = 0; j < sub.size(); j++)
			result.add((sub.get(j) + " " + word).trim());
	}
	cache.put(st, result);
	return result;
}

算法分析：

时间复杂度为O(解大小)，空间复杂度为O(解大小)。

LeetCode

Input: s = “3+2*2”
Output: 7

Input: s = “ 3/2 “
Output: 1

Input: s = “ 3+5 / 2 “
Output: 5

题目大意：

实现字符串加减乘除，但无括号。

算法思路：

逆波兰式的实现用Stack。Stack只存数，而且只存加号操作符的数，也就是说，
核心思想是只有出现运算符，才能计算前一个数[op]num. 所以op和num是记录前一个符号和数字
字符三种类别:空格，数字和运算符
若遇到运算符，就处理四种的op，目标是都要把num压栈，但是op是乘除要计算积或商后才能压栈。压栈后num=0，

如果是减，就将-num入栈，
如果是乘除，立刻计算stack[-1]乘除num的结果再压入栈，因为乘除是最高优先级可以直接计算，而加减不可以。
所以用一个stack

举一个例子: 2+3

1. 2-3+
2. char=”-“的时候, op = “+”, num=”2”. op和num是一对的。
   char=”+”的时候, op = “-“, num=”3”. op和num是一对的。

若5*6+, char=”+”的时候, prev = “5”, op = “*“, num=”6”.
[prev][op][num][char]
stack=只存加号操作符

代码中含三种情况：空格，运算符，数字

LeetCode 224 Basic Calculator 括号加减法, 同一层括号内求和遇括号入栈
LeetCode 227 Basic Calculator II 加减乘除, 和的每一项入栈，方便出栈计乘除
LeetCode 772 Basic Calculator III 加减乘除括号, L227的递归版

注意事项：

此题没有括号，不能用模板，要借用op来记录前一个操作符

1. op记录前一个运算符，char为运算符或当前字符。计算时候根据op，因为char(+)只是第二个操作数(1-2+)的终结字符，此时表明操作数stack[-1], num以及操作符op均已完成，可以计算
2. 最容易错的是向下取整Line 18, 题目返回要求整数。所以要除法后取整int(prev / num)
3. s末尾加入加号，方便parse最后一个num

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def calculate(self, s: str) -> int:
	# prev[op]+num[char]
	# 2-3
	stack, num, op, res = [], 0, '+', 0
	s += "+"
	for c in s:
		if c == " ":
			continue
		if c.isdigit():
			num = 10 * num + int(c) #2
		if c in "+-*/":
			if op == "+":
				stack.append(num)
			if op == "-":
				stack.append(-num)
			if op == "*":
				prev = stack.pop()
				stack.append(prev * num)
			if op == "/":
				prev = stack.pop()
				stack.append(int(prev / num))
			op = c # *
			num = 0
	return sum(stack)

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

LeetCode

initialize iterator with nestedList
res = []
while iterator.hasNext()
    append iterator.next() to the end of res
return res

Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Input: nestedList = [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

题目大意：

实现Nested List的Iterator。Nested List是NestedInteger的数组，NestedInteger可以是int，也可以是Nested List
nestedList = [NestedInteger]
NestedInteger 用isInteger()来判断
-> 2 by getInteger()
-> [2, 3] by getList()

解题思路：

有点似括号题但区别是从前往后读取。用Queue或Stack都可以，插入或删除其一需要反序，删除nestedinteger(=list)后要将它里面所有nestedinteger加入。Queue要从队首加入和删除，Stack要从栈顶加入和删除，用Stack比较方便。

Nested List题目：
LeetCode 341 Flatten Nested List Iterator Iterator - Stack
LeetCode 339 Nested List Weight Sum - BFS
LeetCode 364 Nested List Weight Sum II - BFS

解题步骤：

1. Iterator题目都是用Stack，比如BST Iterator
2. init和next都可以假设是用int来完成，用reversed加入
3. next或hasNext要迭代到第一个integer为止
4. hasNext和next要对第三步保持一致: next要call self.hasNext()

注意事项：

1. 用Stack，逆序将nestedList中nestedinteger加入到stack，直到栈顶元素为int，hasNext才算结束

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class NestedIterator(TestCases):

    def __init__(self, nestedList: [NestedInteger]):
        self.stack = []
        for n in reversed(nestedList):
            self.stack.append(n)
    
    def next(self) -> int:
        return self.stack.pop() if self.hasNext() else None

    
    def hasNext(self) -> bool:
        while self.stack and not self.stack[-1].isInteger():
            n = self.stack.pop()
            for m in reversed(n.getList()):
                self.stack.append(m)
        return self.stack

算法分析：

next操作时间复杂度为O(V/N)或O(1)，空间复杂度O(L + N), N为所有数，V为nested list数，O(N + V)/N. O(1)如果不存在nested list