KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LintCode 683 Word Break III



Give a dictionary of words and a sentence with all whitespace removed, return the number of sentences you can form by inserting whitespaces to the sentence so that each word can be found in the dictionary.

Example 1:


Input:
“CatMat”
[“Cat”, “Mat”, “Ca”, “tM”, “at”, “C”, “Dog”, “og”, “Do”]
Output: 3
Explanation:
we can form 3 sentences, as follows:
“CatMat” = “Cat” + “Mat”
“CatMat” = “Ca” + “tM” + “at”
“CatMat” = “C” + “at” + “Mat”


Example 2:


Input:
“a”
[]
Output: 0


题目大意：

一个字符串s，被“字典集合”（wordDict）中的单词拼接而成的可能性种数。

解题思路：

这是经典题。如果知道s[0:n-1)很容易知道s[0:n)是否有解，既然和子问题有关，就用DP。

  1. 定义dp[i]为字符串s[0,i)是合法分解种数。
  2. 判断一个字符串是否可以合法分解，方案是尝试在每一位进行分解，若其中一个可分解，即有解，加入到dp[i]中。
    递归式为dp[i] += dp[k] * isWord(s[k:i)), 0 <= k < i.
  3. 方向为从左到右i=0..n, 初始值为dp[0] = 1.

注意事项：

  1. 将两个输入都转换成小写。
  2. dp[n+1]而不是dp[n]，而for循环从1开始。
  3. 递归中dp[i]用+操作符。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int wordBreak3(String s, Set<String> dict) {
	if(s == null || "".equals(s))
		return 0;
	
	Set<String> lowerDict = new HashSet<>();
	for(String c : dict)
		lowerDict.add(c.toLowerCase());
	dict = lowerDict;
	s = s.toLowerCase();
	
	int[] dp = new int[s.length() + 1];
	dp[0] = 1;
	
	// dp[i][j] = sum(dp[i][k] * isWord(s[k,j])), i=0..n-1, j=i..n-1
	// dp[0][n-1] = sum(dp[0][k] * isWord(s[k,n-1]))
	// dp[n] = sum(dp[k] * isWord(s[k,n]))
	for(int i = 1; i <= s.length(); i++) {
		for(int k = 0; k < i; k++) {
			dp[i] += dp[k] * (dict.contains(s.substring(k, i)) ? 1 : 0); 
		}
	}
	return dp[s.length()];
}

算法分析：

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

这道题一开始走过一些弯路，首先我觉得类似于Catalan算法，左右半部都是子问题，但其实这属于单边问题。所以写了以下算法：

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int wordBreak3_wrong(String s, Set<String> dict) {
	if(s == null || "".equals(s))
		return 0;
	
	// dp[i][j] = sum(dp[i][k] * dp[k][j])
	int[][] dp = new int[s.length() + 1][s.length() + 1];
	
	// use "ab" as an example
	for(int len = 1; len <= s.length(); len++) {
		for(int i = 0; i < s.length() - len + 1; i++) {
			for(int j = i + 1; j < i + len; j++) {
				//"a","b"
				dp[i][i+len] += dp[i][j] * dp[j][i+len];    		
			}
			//"ab"
			if(dict.contains(s.substring(i, i+len)))
				dp[i][i+len]++;
			
		}
	}
	return dp[0][s.length()];
}

但这个方法会有重复解，比如
“abc”, “a”,”b”,”c”
-> dp["ab"] * dp["c"] = 1
-> dp["a"] * dp["bc"] = 1
所以解重复，因为这问题是单边子问题而不是Catalan问题。
更改版本为单边子问题，一开始用dp[n]导致初始化稍复杂，其实初始化可以并入到递归式，只要用dp[n+1]即可。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int wordBreak32(String s, Set<String> dict) {
	if(s == null || "".equals(s))
		return 0;
	
	int[] dp = new int[s.length()];
	for(int i = 0; i < s.length(); i++)
		dp[i] = dict.contains(s.substring(0, i + 1)) ? 1 : 0;

	for(int i = 0; i < s.length(); i++) {
		for(int k = 0; k < i; k++) {
			dp[i] += dp[k] * (dict.contains(s.substring(k + 1, i + 1)) ? 1 : 0); 
		}
	}
	return dp[s.length() - 1];
}

Posted on Edited on Disqus:

LeetCode 139 Word Break



Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = “leetcode”, wordDict = [“leet”, “code”]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".


Example 2:

Input: s = “applepenapple”, wordDict = [“apple”, “pen”]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.


Example 3:

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


题目大意：

一个字符串s，是否能够被“字典集合”（wordDict）中的单词拼接而成。

解题思路：

这是经典题。如果知道s[0:n-1)很容易知道s[0:n)是否有解，既然和子问题有关，就用DP。

  1. 定义dp[i]为字符串s[0,i)是否可以合法分解。
  2. 判断一个字符串是否可以合法分解，方案是尝试在每一位进行分解，若其中一个可分解，即有解。
    递归式为dp[i] |= dp[k] && isWord(s[k:i)), 0 <= k < i.
  3. 方向为从左到右i=0..n, 初始值为dp[0] = true.

注意事项：

  1. 初始值dp[0] = True。
  2. 递归中dp[i]用或操作符。
  3. s[j:i] in word_set不要忘记上限为i

Python代码：

1
2
3
4
5
6
7
8
9
10
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
	if not s:
		return False
	word_set = set(wordDict)
	dp = [False] * (len(s) + 1)
	dp[0] = True
	for i in range(1, len(dp)):
		for j in range(0, i):
			dp[i] |= dp[j] and s[j:i] in word_set
	return dp[len(dp) - 1]

注意事项：

  1. 将两个输入都转换成小写。
  2. 递归中dp[i]用或操作符。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean wordBreak(String s, List<String> wordDict) {
	if(s == null || s.isEmpty() || wordDict == null || wordDict.size() == 0)
		return false;
	Set<String> wordDictLower = new HashSet<>();
	for(String c : wordDict)
		wordDictLower.add(c.toLowerCase());
	s = s.toLowerCase();
	
	boolean[] dp = new boolean[s.length() + 1];
	dp[0] = true;
	for(int i = 1; i < dp.length; i++)
		for(int k = 0; k < i; k++) {//"a"
			dp[i] |= dp[k] && wordDictLower.contains(s.substring(k, i));
		}
	return dp[dp.length - 1];
}

算法分析：

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

算法II解题思路：

这题也可以额用DFS来解。如果可以用DP就尽量用DP，只有求所有可能性才只能用DFS而不能用DP。
这道题递归子问题dfs[:n]为子串[0:n)是否可合法拆解。对于子问题而言，需要对其范围内i=[0:st)的每个可能位置分解
dfs[:i) + word[i:st)从而求出dfs(st)的解，只有任一分解成功，dfs(st)=true，否则false。

Cache的应用场景： 如果子问题重复就要用Cache。
例如dfs(10)=dfs(9)+s[9:9] = (dfs(8) + s[8:8]) + s[9:9]
=dfs(8)+s[8:9]
dfs(8)由第一层递归第二个循环s[8:9]和第二层递归s[9:9]达到，这是重复的子问题dfs(8)。如果不cache，dfs(8)的求解
是重复的。

Cache模板：

  1. key为子问题索引st，value为子问题的解。
  2. 紧跟终结条件，若在cache中，返回子问题的解。
  3. 循环结束，将子问题的结果存于cache。

注意事项：

  1. 将两个输入都转换成小写。
  2. 递归中先查询词是否在字典中再递归。如果顺序调转就会LTE，因为这些子问题是白费的。
  3. 递归终结条件为st==0而不是st==s.length()因为子问题递归从右到左。

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
public boolean wordBreakDFS(String s, List<String> wordDict) {
	if(s == null || s.isEmpty() || wordDict == null || wordDict.size() == 0)
		return false;
	Set<String> wordDictLower = new HashSet<>();
	for(String c : wordDict)
		wordDictLower.add(c.toLowerCase());
	s = s.toLowerCase();
	Map<Integer, Boolean> cache = new HashMap<>();
	return dfs(s, wordDictLower, s.length(), cache);
}

// subproblem's answer dfs[:st)
boolean dfs(String s, Set<String> wordDict, int st, Map<Integer, Boolean> cache) {
	if(st == 0)
		return true;
	if(cache.containsKey(st))
		return cache.get(st);
	boolean re = false;
	for(int i = 0; i < st; i++) {
		if(wordDict.contains(s.substring(i, st)) && dfs(s, wordDict, i, cache))
			return true;
	}
	cache.put(st, re);
	return false;
}

算法分析：

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

Posted on Edited on Disqus:

LeetCode 146 LRU Cache



Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 / capacity / );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4


题目大意：

设计LRU。就是最就的cache会先被删除。

解题思路：

因为是Cache，get是O(1)，自然想到用HashMap。如果不限容量，get，put都可以O(1)。限容量的情况下，
就要删除部分数据，这里要求按key的时间排序，所以考虑用一个串将keys串联起来。而key的添加和删除
也要O(1)，所以考虑用LinkedList。HashMap和LinkedList的组合很常见。这里value就指向LL中的Node，
而Node中含key和value，key又可以让Node只向HashMap，做到互相索引。分析get和set，get就只要从Map
中读Node的value即可。set比较复杂，含三种情况：

  1. 已有节点
  2. 不含节点且少于容量
  3. 不含节点且大于等于容量

对应链表操作为：

  1. 删除该节点且插入到末尾（LL顺序为由旧到新）
  2. 插入新节点到末尾
  3. 删除头节点且插入新节点到末尾

总结链表操作为两个：

  1. 删除某节点
  2. 插入新节点到末尾

实现上可以分为单链表和双链表。单链表要让Map指向节点的父节点。实现上很麻烦，因为更新节点都会涉及
两个keys上HashMap更新，即使已有节点换到末尾同样要两次更新Map。但双链表对此情况就避免了Map的更新。

DummyNode的选择：一开始我只选用了DummyHead，但capacity=1的时候要判断末节点是否为空很麻烦，由于
经常性的插入末节点，所以根据若头结点涉及插入删除就应该用dummyNode的原则，末节点也增加dummyNode
程序就简洁很多。

有些解法用单链表，用node映射到对应节点的父节点key_to_prev，这个方法反而不好理解，写的时候也容易错，不推荐

注意事项：

  1. set中，若节点存在，更新value。更新节点在链表中的顺序。注意三种情况，已有节点以及不含节点的两种。
  2. 头尾dummy node，初始化要相连。
  3. 注意删除顺序，先删map中的entry再删Node。否则会出现NPE。新加入是顺序相反。删除节点要将prev和next赋None
  4. 双向LL加入新节点有两个赋值语句，不要忘记node.prev, node.next = predecessor, successor

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class LRUCache:

    def __init__(self, capacity: int):
        self.key_to_node = {}
        self.capacity = capacity
        self.head = ListNode(0, 0)
        self.tail = ListNode(0, 0)
        self.head.next, self.tail.prev = self.tail, self.head

    def get(self, key: int) -> int:
        if key not in self.key_to_node:
            return -1
        self.move_to_tail(self.key_to_node[key])
        return self.key_to_node[key].val

    def put(self, key: int, value: int) -> None:
        if key in self.key_to_node:
            self.key_to_node[key].val = value
            self.move_to_tail(self.key_to_node[key])
        else:
            if len(self.key_to_node) == self.capacity:
                self.key_to_node.pop(self.head.next.key)
                self.remove_node(self.head.next)

            node = ListNode(key, value)
            self.add_to_tail(node)  # add_to_tail(node)
            self.key_to_node[key] = node

    def move_to_tail(self, node):
        self.remove_node(node)
        self.add_to_tail(node)

    def add_to_tail(self, node):
        predecessor, successor = self.tail.prev, self.tail
        predecessor.next, node.prev = node, predecessor
        node.next, successor.prev = successor, node

    def remove_node(self, node):
        predecessor, successor = node.prev, node.next
        predecessor.next, successor.prev = successor, predecessor
        node.prev, node.next = None, None


class ListNode:
    def __init__(self, key, val, next = None, prev = None):
        self.val = val
        self.key = key
        self.next = next
        self.prev = prev

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
Map<Integer, ListNode> map;
ListNode head; // from oldest to newest
ListNode tail;
int capacity;
public L146LRUCache(int capacity) {
	this.capacity = capacity;
	head = new ListNode(-1, -1);
	tail = new ListNode(-1, -1);
	head.next = tail;
	tail.prev = head;
	map = new HashMap<>();
}

public int get(int key) {
	if(!map.containsKey(key))
		return -1;
	pushback(key);
	return map.get(key).val;
}

public void put(int key, int value) {
	if(map.containsKey(key)) {
		pushback(key);
		map.get(key).val = value; // remember to update the value
	}
	else {
		if(map.size() == capacity) {
			map.remove(head.next.key);
			deleteNode(head.next);
		}
		// add new key
		ListNode newNode = new ListNode(key, value);
		addNodeToTail(newNode);
		map.put(key, newNode);
	}
}

void pushback(int key) {
	ListNode curNode = map.get(key);
	deleteNode(curNode);
	addNodeToTail(curNode);
}

void addNodeToTail(ListNode curNode) {
	ListNode prevTailNode = tail.prev;
	prevTailNode.next = curNode;
	curNode.prev = prevTailNode;
	curNode.next = tail;
	tail.prev = curNode;
}
// delete head node and updated node
void deleteNode(ListNode curNode) {
	ListNode nextNode = curNode.next;
	ListNode prevNode = curNode.prev;
	prevNode.next = nextNode;
	nextNode.prev = prevNode;
	curNode.next = null;
	curNode.prev = null;
}

public class ListNode {
	public int key;
	public int val;
	public ListNode next;
	public ListNode prev;

	public ListNode(int key, int val) {
		this.key = key;
		this.val = val;
	}
}

算法分析：

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

Posted on Edited on Disqus:

LeetCode 126 Word Ladder



Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

Return an empty list if there is no such transformation sequence. All words have the same length.
All words contain only lowercase alphabetic characters. You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]

Output:
[
  [“hit”,”hot”,”dot”,”dog”,”cog”],
  [“hit”,”hot”,”lot”,”log”,”cog”]
]


Example 2:

Input:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”]

Output: []

*Explanation:
 The endWord “cog” is not in wordList, therefore no possibletransformation.


题目大意：

给定一个字典和两个单词。每次变换一个字母的得到新单词且该词要在字典中。求所有最少的变换路径。

解题思路：

更难于Leetcode 127，BFS用于找最短路径而DFS找路径，此题正是贯彻这一思想，先用BFS找出最短路径，
然后根据最短路径值找出所有路径。找BFS解的同时建图用邻接表表示Map>(这是
部分图，与解相关的图)和解集合Map(从始点到不同节点的最短距离)，这两个信息正是
Dijkistra的图输入和解。DFS从始点开始遍历邻接节点，确保沿着最短路径走，最短路径为
map.get(cur)+1=map.get(next)表示当前节点到始点距离+1=儿节点到始点距离，终止条件为找到目标节点。

  1. 在遍历所有邻接节点的时候，如果不加筛选对所有邻接节点都做DFS会造成LTE。关键是要利用BFS中所有
    节点到单源的最短路径来剪枝。只需DFS最短路径上的节点，否则跳过。
  2. 利用了单源最短路径映射表distance后，不需要记录visited，因为重复的节点不会在最短路劲上。
  3. Cache nextWords的结果。

解题步骤：

这题是最短路径题，第一时间想到BFS。这是一条典型的单源最短路径问题。

  1. 建字典。
  2. BFS访问，得到图和单源最短路径Map，以及最短路径距离。同时建立邻接表graph[word] = neighbors，DFS时候不用再次找相邻单词
  3. DFS求路径，按最短路径剪枝dict[neighbor] == dict[startWord] + 1。

注意事项：

  1. 注意题目条件，开始词不在字典中(终结词默认在，否则无结果），要将它加入字典中且距离为1且要加入到path，Line 10。
  2. 建图的邻接表，对没有边的节点也要加到邻接表，所以先对所有点赋空列表，再根据边更新值，Line 29。用defaultdict(list)可解决
  3. DFS模板中去掉visited部分，因为用了最短距离distance的map来指导访问路径，所以不会存在循环的情况(否则不会是最短距离)
    而且如果有visited会存在丢解，因为如果一个节点不在最短路径上先被访问就会被标记为visited，真正到最短路径上时就会返回。
    DFS模板中加入if dict[neighbor] == dict[startWord] + 1来剪边。

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[int]]:
	if not beginWord or not endWord:
		return 0
	distance, graph = {}, defaultdict(list)
	for word in wordList:
		distance[word] = 0
	distance[beginWord] = 1
	self.bfs(beginWord, endWord, distance, graph, set())
	result = []
	self.dfs(graph, beginWord, endWord, [beginWord], result, distance) # remember [beginWord]
	return result

def dfs(self, graph, startWord, endWord, path, res, dict):
	if startWord == endWord:
		res.append(list(path))
		return
	'''if startWord in visited: # remember
		return
	visited.add(startWord)'''
	for neighbor in graph[startWord]:
		if dict[neighbor] == dict[startWord] + 1:
			path.append(neighbor)
			self.dfs(graph, neighbor, endWord, path, res, dict)
			path.pop()

def bfs(self, beginWord, endWord, dict, graph, visited):
	queue = deque([beginWord])
	visited.add(beginWord)
	# for key in dict.keys():  # remember
	#    graph[key] = []
	while queue:
		word = queue.popleft()
		if word == endWord:
			return dict[word]

		neighbors = self.get_next_words(word, dict)
		graph[word] = neighbors
		for neighbor in neighbors:
			if neighbor not in visited:
				queue.append(neighbor)
				visited.add(neighbor)
				dict[neighbor] = dict[word] + 1
	return 0

def get_next_words(self, word, dict):
	res = []
	for i in range(len(word)):
		for c in string.ascii_lowercase: # or use 'abcdefghijklmnopqrstuvwxyz'
			if c == word[i]:
				continue
			new_word = word[:i] + c + word[i + 1:]
			if new_word in dict:
				res.append(new_word)
	return res

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
	List<String> path = new ArrayList<>();
	List<List<String>> res = new ArrayList<>();
	if(beginWord == null || endWord == null)
		return res;
	
	// This is a dict and also keeps track of distance
	Map<String, Integer> dict = getDict(wordList);
	// Make sure endWord is in the dict and can be the next word 
	//dict.put(endWord, 0);
	dict.put(beginWord, 1);
	HashMap<String, List<String>> graph = new HashMap<String, List<String>>();
	ladderLength(beginWord, endWord, dict, graph);
	path.add(beginWord);
	dfs(beginWord, endWord, dict, graph, path, res);
	return res;
}

void dfs(String cur, String endWord, Map<String, Integer> distance,
		HashMap<String, List<String>> graph, List<String> path, List<List<String>> res) {
	if(endWord.equals(cur)) {
		res.add(new ArrayList<>(path));
		return;
	}
	for(String word : graph.get(cur)) {
		path.add(word);
		if(distance.get(word) - 1 == distance.get(cur)) // use distance, resolve LTE the most important
			dfs(word, endWord, distance, graph, path, res);
		path.remove(path.size() - 1);
	}
}

// cache getNextWords
int ladderLength(String beginWord, String endWord, Map<String, Integer> dict, Map<String, List<String>> graph) {
	Set<String> visited = new HashSet<>();
	Queue<String> q = new LinkedList<>();
	q.offer(beginWord);
	visited.add(beginWord);
	for(String s : dict.keySet()) {// remember
		graph.put(s, new ArrayList<>());
	}
	while(!q.isEmpty()) {
		String word = q.poll();
		if(endWord.equals(word))
			return dict.get(word);
		
		List<String> nextWords = getNextWords(word, dict);
		graph.put(word, new ArrayList<>(nextWords));
		for(String s : nextWords) {
			if(visited.contains(s))
				continue;
			
			q.offer(s);
			visited.add(s);
			dict.put(s, dict.get(word) + 1);
		}
	}
	return 0;
}

Map<String, Integer> getDict(List<String> wordList) {
	Map<String, Integer> map = new HashMap<>();
	for(String word : wordList) {
		map.put(word, 0);
	}
	return map;
}

List<String> getNextWords(String word, Map<String, Integer> dict) {
	List<String> result = new ArrayList<>();
	for(int i = 0; i < word.length(); i++) {
		for(int j = 0; j < 26; j++) { 
			char newChar = (char)('a' + j);
			if(word.charAt(i) == newChar) // exclude itself
				continue;
			String newWord = word.substring(0, i) + 
					newChar + word.substring(i + 1, word.length());
			if(dict.containsKey(newWord))
				result.add(newWord);
			
		}
	}
	return result;
}

算法分析：

getNextWords是L26L=O(L2)产生新字符串需要L
时间复杂度为O(nL2 + mk)，空间复杂度O(n)，m为答案个数, k为最短路径值，n为单词数。

Posted on Edited on Disqus:

算法思路：

Leetcode 078的题目。这里作为知识点归纳。

  1. 递归中i=st开始。
  2. 回溯： path递归后去恢复状态。
  3. dfs中传入i+1。
  4. 结果要复制new ArrayList<>(path)
  5. 一般来说，终止条件才加入结果，但由于子集任何path修改都是子集，所有立即加入。

和全排列的区别：

  1. 由于排列可以乱序如[1,2,3]结果是[1,3,2]也就是一个结果需要多次从左向右完全扫描，所以i=0开始且维护visited数组
    组合的结果是按照数组顺序的，所以只要从左到右扫描一次即可，所以用i=st。
  2. 结果方面，排列结果是满长度，而组合不是。所以在加入到res位置上，组合用st来判断是否结束且加入到path就立刻进入最后
    结果，而排列是在终结条件上加入。

应用：

  1. 找所有可能性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def combine(self, nums: List[int]) -> List[List[int]]:
	if not nums:
		return [[]]
	path, result = [], []
	self.dfs(nums, 0, path, result)
	return result

def dfs(self, nums, st, path, result):
	if st == len(nums):
		return

	for i in range(st, len(nums)):
		path.append(nums[i])
		result.append(list(path))
		self.dfs(nums, i + 1, path, result)
		path.pop()

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<List<Integer>> subsets(int[] nums) {
	List<Integer> path = new ArrayList<>();
	List<List<Integer>> res = new ArrayList<>();
	res.add(new ArrayList<>(path)); //empty set
	if(nums == null || nums.length == 0)
		return res;
	dfs(nums, 0, path, res);
	return res;
}

void dfs(int[] nums, int st, List<Integer> path, List<List<Integer>> res) {
	if(st == nums.length)
		return;
	
	for(int i = st; i < nums.length; i++) {
		path.add(nums[i]);
		res.add(new ArrayList<>(path));
		dfs(nums, i + 1, path, res);
		path.remove(path.size() - 1);
	}
}

算法分析：

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

Free mock interview