LeetCode
题解 - Solutions
数组与字符串 - Array and Strings
1. Two Sum
-
描述
给定一个整型数组和一个目标数，返回整型数组中两个数的和为目标数的下标（题目保证有解，数组中每一个数只能使用一次。
-
题解
初始化字典
dic，其键值为数组中某元素与其下标，遍历数组中每个元素arr[i]，目标值target与arr[i]的差记为diff，在dic中查找键diff，如果存在，则返回diff的下标与i，如果不存在，为dic建立arr[i]与i的键值对。
125. Valid Palindrome
8. String to Integer
344. Reverse String
20. Valid Parentheses
-
描述
给定一个字符串表达式，判断表达式中的括号是否合法，一个合法的括号应该像：{[()]}，这样的形式。
-
题解
维护一个栈，记作
stack，然后遍历字符串，如果遇到左括号字符，则将该字符入栈，如果遇到右括号字符，则将栈顶出栈，判断括号是否匹配，如果匹配失败，则返回False，如果匹配成功，则继续遍历直到结束。如果遍历结束，栈不为空，则匹配失败，否则匹配成功。
5. Longest Palindromic Substring
-
描述
给定一个字符串，返回这个字符串的最大回文子串。
-
题解
由于枚举所有长度的子串，并判断该子串是否是回文子串的复杂度（
O(n * m * m)）过高，故考虑动态规划。在外层循环以下标j遍历字符串下标，j代表了子串的右界（0 <= j <= len(s)），内层循环以下标i遍历子串下标（0 <= i <= j），易知，当j=i时，原字符串s的子串sub_s，即s[i:j+1]是回文的，而当j-i=1时，如果s[i]=s[j]则子串sub_s，是回文的，而当j-i>1时，子串sub_s是否回文，取决于是否s[i]=s[j]且s[i+1:j-1]是否为真，如果为真，则sub_s回文。所以，我们维护一个dp二维数组，其下标i,j表示原字符串从下标i开始到j结束（包含j）的子串是否为回文子串。在便利过程中不断更新最长的下标i, j最后返回最长回文子串。
49. Group Anagrams
-
描述
给定一个字符串型数组，将具有相同字符组成的字符串分别保存为一个字符串型数组，返回一个字符串型数组型的数组，作为结果。
-
题解
维护一个字典记作
dic，其键值分别为按字典序排序后的字符串和字符串型数组。遍历字符串型数组，对每一个字符串s，按字典序排序，结果记作s_sorted，在dic中取s_sorted的值res，res是一个字符串型的数组，然后将s添加进res，最后返回dic的values作为结果。
42. Trapping Rain Water
-
描述
接雨水，给定一个整型数组
height，数组内每个元素的值代表了“墙”的高度，墙的高度差可以用来储水，求给定一组墙高，能储多少水。 -
题解
首先遍历
height，找到最高“墙”的下标i_max_height，初始化一个i_cur_peak=0代表当前“左高峰”，然后从左到i_max_height遍历墙高，期间，如果当前“左高峰”小于当前墙高，则更新“左高峰”，否则，更新雨水总量rain+=i_cur_peak-height[i]，即“左高峰”减去当前墙高，直到遍历到墙的最高处为止。然后从右到i_max_height遍历墙高，逻辑同上。最后返回雨水总量。
15. 3Sum
-
描述
给定一个整型数组
num，例如[-1, 0, 1, 2, -1, -4]，返回一组结果，每个结果是一个数组，满足：在nums中选3个数字，这3个数字的和为0，过滤重复解。 -
题解
首先，3个数字
a, b, c的和为0，即a + b = c，则将问题转化为了一个Two Sum问题，所以，我们先排序数组nums，并初始化targets数组：[-num for num in nums]。以下标i进入循环，初始化y_map与target = targets[i]，y_map用来记录是否y已经查找过。然后遍历nums[i + 1:]的每一个元素x，将target - x记作y，如果y在y_map中，则添加结果-target, x, y作为一个解。否则，y_map[x] = x，记录当前x到y_map字典中。最后去重结果并返回。
48. Rotate Image
-
描述
给定一个二维数组
matrix，将它顺时针旋转90°，不可以申请新空间。 -
题解
首先，将
matrix转置，以i, j为行列，进入循环，即对于每一个元素matrix[i][j] = matrix[j][i]，需注意，此处j从i开始，因为只需遍历matrix的上三角矩阵即可。然后，再将转置的矩阵martix水平翻转，即以i, j为行列进入循环，使得matrix[i][j] = matrix[i][num_col - j - 1]，需要注意，j的上界是num_col // 2，因为num_col // 2为轴心。
66. Plus One
-
描述
给定一个数组
nums，如[1, 2, 3]，代表了123的各位，现在对个位加一，返回结果数组，如[1, 2, 4]。 -
题解
初始化
carry进位标识符，首先对个位加一，如果结果大于10，则模10后标记carry = 1，然后遍历剩余的位数加carry，同时判断是否进位，直到遍历结束。如果遍历结束后carry = 1，则插入1到数组下标为0处。
189. Rotate Array
215. Kth Largest Element in an Array
76. Minimum Window Substring
-
描述
给定原始字符串
s与目标字符串t，返回一个最小窗口字符串sub_s，该窗口字符串是最小的字符串包含了目标字符串t所有字符。 -
题解
首先初始化两个字典记作
start_dic和end_dic，它们的键值分别为字符和出现的次数，然后遍历t中的每一个字符，更新这两个字典。然后计算t的长度记为t_length。初始化下标start = 0，然后以end = 0为下标遍历s，end表示s的右边界，如果s[end]在end_dic中，而且end_dic[s[end]] > 0，则将start_dic[s[end]]自减，同时，如果start_dic[s[end]] >= 0，则将t_length自减，如果t_length == 0，则进入以下循环：如果s[start]在end_dic中，而且end_dic[s[start]] > 0，如果start_dic[s[start]] < 0则start_dic[s[start]]自增，否则break，start += 1，然后根据当前最小窗口大小min_size是否大于end - start + 1来更新最小窗口大小min_size，和结果起始下标min_start。最终，如果min_size < len(s) + 1，则返回s[min_start: min_start + min_size]，否则返回空串。
链表 - Linked List
206. Reverse Linked List
-
描述
给定一链表，将它就地逆序。
-
题解
初始化前驱节点
pre_node=None，通过head_node遍历链表，通过cur_node临时存储head_node，然后更新head_node = head_node.next，接着更新当前节点的后继节点为前驱节点，cur_node.next = pre_node，最后将前驱节点更新为当前节点，pre_node = cur_node，直到遍历结束，最终返回pre_node为逆序后的头结点。
141. Linked List Cycle
-
描述
给定一个链表，判断链表是否存在“环”
-
题解
分别维护快慢指针，初始化为
s_node, f_node = head, head.next，以快慢指针都为真的条件进入while循环，如果快指针与慢指针地址相等，则存在环，否则更新慢指针，s_node=s_node.next，更新快指针两次，f_node=f_node.next，if f_node: f_node = f_node.next，继续循环，如果循环结束，则不存在环。
2. Add Two Numbers
-
描述
给定两个链表，它们从头节点到尾节点分别表示数字的最低位到最高位，求将两链表相加的结果链表。
-
题解
初始化进位记录标识符
count=0与结果头节点head，以两链表为真的条件进入循环，将当前节点结果相加，并加count后，模10，如果进位，则将count记为1，并保存结果cur_node.next = Node(x)，然后更新cur_node=cur_node.next，直到循环结束。如果仍有较长链表遍历未结束，则遍历该链表，依次将其节点与count相加后添加在结果节点的cur_node后，直到遍历结束，最后检查进位是否需要需要创建新节点，并返回结果头节点。
21. Merge Two Sorted Lists
-
描述
给定两个有序链表，将他们合并成新的有序链表，并返回这个链表的头节点。
-
题解
初始化新头节点与当前节点记为
head_node与cur_node，以两链表为真的条件进入循环，比较两链表的当前值，将值小的节点添加为cur_node的后继节点，然后更新该节点为之后继，然后更新cur_node=cur_node.next，直到循环结束。循环结束后，如果仍有链表为真，则将剩余部分作为cur_node的后继，然后返回头节点。
23. Merge k Sorted Lists
树和图 - Trees and Graphs
98. Validate Binary Search Tree
94. Binary Tree Inorder Traversal
-
描述
给定一颗二叉树，输出中根遍历结果。
-
题解
初始化栈
stack，将元组(root, False)入栈，以栈不为空进入循环，将栈顶元组出栈，结果记为cur_node, visited，如果cur_node为真时，visited为真，即已经访问了该节点，则将该节点的值cur_node.val添加到结果数组，如果visited为假，即尚未访问该节点，则依次将该节点的右节点，该节点，该节点的左节点入栈，他们的访问标记分别为False, True, False，然后继续循环。最后打印结果。
102. Binary Tree Level Order Traversal
-
描述
给定一颗二叉树，输出层序遍历结果。
-
题解
初始化层节点数组
level_nodes=[root]，以层节点数组不为空为条件进入循环，向结果数组添加层节点数组内所有节点的值，然后初始化临时层节点数组tmp_level_nodes，遍历当前层节点的所有节点，添加他们的左右孩子节点（需为真），然后更新level_nodes=tmp_level_nodes，直到循环结束，最后返回结果数组。
103. Binary Tree Zigzag Level Order Traversal
116. Populating Next Right Pointers in Each Node
-
描述
给定一颗满二叉树，将二叉树的每一层变成一个链表（二叉树的节点数据结构已经有
next成员变量） -
题解
同上，在更新
level_nodes==tmp_level_nodes后，遍历之，node.next = next_level_nodes[index + 1]更新后继节点。
117. Populating Next Right Pointers in Each Node II
235. Lowest Common Ancestor of a Binary Search Tree
-
描述
给定一颗二叉搜索树与其两个节点，返回这两个节点的最小公共祖先。
-
题解
利用二叉搜索树性质并递归，如果两个节点的值
pval, qval都小于root.val，那么公共祖先一定在root节点的左子树中，所以递归调用当前函数，根节点，即二叉查找树为root.left。相反，如果pval, qval都大于root.val，则公共祖先一定在root节点的右子树中，执行上述操作。最终，如果qval < root.val < pval，则root为最小公共祖先。
236. Lowest Common Ancestor of a Binary Tree
-
描述
给定一颗二叉树与其两个节点，返回这两个节点的最小公共祖先。
-
题解
初始化
p_path, q_path分别保存先根遍历到p, q节点的路径。路径是指使用先根遍历，遍历该二叉树，直到某个节点的值等于目标节点的值node.val==target.val，并将完成标记flag=Ture，并将其他遍历结果移出路径，如何保存路径，请参见257. Binary Tree Paths。然后遍历两个路径p_path, q_path，最后一个相同的节点，即是最小公共祖先。
105. Construct Binary Tree from Preorder and Inorder Traversal
-
描述
已知一颗二叉树的先根和中根遍历结果，恢复二叉树。
-
题解
利用递归，以中根遍历结果数组不为空的条件进入函数，将先根数组
pre_vals的首个节点值root_val出队列，并求出root_val在中根遍历数组中的下标，记为root_index，易知，中根遍历数组中，该节点下标左边的值均为其左子树的值，该下标右边的值均为其右子树的值。创建节点root=TreeNode(root_val)，而root.left则递归本函数，入参分别为pre_vals与in_vals[: root_index]，而root.right则递归本函数，入参分别为pre_vals与in_vals[root_index + 1:]，最后返回根节点。
200. Number of Islands
-
描述
描述较为复杂，概述为寻找一个
0-1矩阵中“孤岛”，即1构成的块的个数。 -
题解
维护一个
visited数组，描述了某个下标i, j是否已经访问过，以下标i, j分别代表行列遍历图，如果图中grid[i, j] == 1，则进行深度优先遍历，需注意深度优先遍历的条件，即0<=i<=row, 0<=j<=col。如果i, j已经访问过，或者grid[i, j]==0则返回0，否则将本次遍历区域加1，并将visited[i, j]=1后，继续遍历，方向为上、下、左、右。最后以所有行列i, j为入口遍历完毕后，返回累计结果。
257. Binary Tree Paths
-
描述
给定一颗二叉树，输出先根遍历到所有叶子节点的路径字符串。
-
题解
初始化临时路径
path与结果路径集合paths，先根遍历二叉树，遍历的过程中，每访问一个节点，如果该节点为空，则返回，否则将其添加到临时路径path中，并检查该节点是否有左右孩子节点，如果没有，则执行一次path临时路径到结果路径的序列化，结果添加到paths中。如果有左右孩子节点，则继续对该节点的左右孩子进行先根遍历。如果访问到叶子节点，则对path执行pop操作，将该节点出栈。最后返回结果路径集合paths。
695. Max Area of Island
-
描述
给定一个二维数组
grid，其元素为0或1，找到最大的“孤岛”，并返回其大小。 -
题解
维护
result变量记录结果，维护一个二维数组visited，vistied[i][j]描述了grid[i][j]是否已经被访问过，然后对以i, j为下标进入循环，对grid[i][j]进行深度优先遍历。在深度优先遍历时，维护一个res = 1变量，如果grid[i][j] == 0，则返回0，如果grid[i][j] == 1，才能继续遍历，同时，将visited[i][j] = 1，并将res += 1，然后进行方向为上、下、左、右的深度优先遍历。如果res > result，则更新result = res，最后返回result作为结果。
547. Friend Circles
-
描述
给定一个二维数组
M，其中元素为0或1，表示第j个人是否是第i个人的直接朋友。如果k是j的朋友，j是i的朋友，则i与k是间接朋友，它们形成了一个“朋友圈”，求M中朋友圈的个数。 -
题解
维护一个
visited数组，表示是否已经检查过第i个人的朋友圈。然后以i为第i个人的下标，进入循环，如果visited[i] == 1，即已经检查过该人的朋友圈，则continue，否则，首先将visited[i] = 1，然后初始化栈stack = [i]，准备深度优先遍历：当栈stack不为空，则栈尾出栈记作j，则以k为第k个人的下标，进入循环，如果visited[k] == 0且M[j][k] == 1，即第k个人的朋友圈尚未检查，而且j与k互为朋友，则将k入栈。当以i为下标的外部循环结束，则将res += 1，结果自增。最后返回res作为结果。
104. Maximum Depth of Binary Tree
回溯 - Backtracking
17. Letter Combinations of a Phone Number
-
描述
数字
2-9中，每个数字对应电话号码上的几个字母，给定一个由2-9组成的字符串，输出所有可能的字母组合。 -
题解
初始化结果数组
result，对给定数字字符串s以及每个字符所能对应的字母，进行深度优先遍历。即，遍历数字字符串s，对每一个下标i，与其对应的数字num，查询它可能的组成字母，依次递归调用深度优先遍历函数。深度优先遍历函数有四个参数，分别是当前下标i，数字字符串s，当前组合pattern，结果数组result，直到当前下标i == len(s)时，将pattern添加到result中，并返回结果数组。
39. Combination Sum
-
描述
给定一个整形数组，所有元素均为正数，记作
candiates，给定一个目标数记作target，在candiates找到所有整数的组合，使他们的和等于target，每个元素可以使用多次。 -
题解
首先排序
candidates，然后设计深度优先遍历函数dfs(candidates, target, last_num, result, results)。即，target == 0，则添加result到结果数组results，如果target < candidates[0]，则返回。然后遍历candidate的每一个数字记作num，对每一个num，如果它大于target，则返回。如果它小于last_num，则continue，因为这个数字应该已经被遍历过了。否则，将num添加到临时result，然后递归调用dfs(candidates, target - num, num, result, results)，最后通过result.pop()当前num，全部结束后返回results。
排序和搜索 - Sorting and Searching
26. Remove Duplicates from Sorted Array
-
描述
给定一个已经排序的数组，数组中可能有重复元素，就地移除重复元素，并返回新的数组长度。
-
题解
初始化有序下标
j == 0，以下标i = 0开始遍历排序数组nums，如果排序数组nums在有序下标j的值不等于在下标i的值，则将j += 1，并使得nums[j] = nums[i]。如果排序数组nums在有序下标j的值等于下标i的值，则什么都不做。最后返回j + 1作为结果。
88. Merge Sorted Array
-
描述
给定两个排序后的数组
a, b，其中a数组足够长，归并两个排序数组至a数组并返回。 -
题解
从后遍历数组
a, b，初始化三个下标a_i == len(a) - 1，b_i == len(b) - 1,m_i = len(a) + len(b) - 1，分别代表a的下标，b的下标，结果下标，以a_i, b_i均大于等于0进入循环，如果a[a_i] > b[b_i]，则a[m_i] = a[a_i]，然后m_i -= 1，a_i -= 1，反之同理，直到循环结束。如果b_i仍大于等于0，则说明b仍有剩余，这些数字都很小，所以以b_i大于等于0为条件进入循环，依次a[m_i] = b[b_i]，然后m_i -= 1，然后b_i -= 1，最后结束。
75. Sort Colors
-
描述
三色排序，给定一个整型数组
nums，只包含0, 1, 2三种元素，以O(n)的时间就地排序，不可使用基数排序，后返回结果。 -
题解
初始化三个下标
i == 0, j == len(nums) - 1, k == 0，分别代表左下标，右下标，当前下标。然后k < j，即当前下标小于右下标为条件进入循环，如果nums[k] == 2，则交换num[k]与num[j]的值，然后j -= 1，即右下标左移。如果nums[k] == 1，则k += 1。如果nums[k] == 0，则交换num[k]与nums[i]的值，然后i += 1, k += 1，直到循环结束。
153. Find Minimum in Rotated Sorted Array
-
描述
给定一个有序数组
nums，数组在某一位被翻转，例如：如[0, 1, 2, 3, 4] -> [3, 4, 0, 1, 2]，返回最小元素。 -
题解
初始化三个下标
i == 0, j == len(nums) - 1, mid == 0，分别代表左下标，右下标，中下标。然后以i < j为条件进入循环，计算mid = (i + j) // 2，如果nums[mid] < nums[j]，则说明区间有序，更新j = mid，继续循环。如果nums[mid] >= nums[j]，则说明区间内存在翻转，最小元素应在翻转区间，将i = mid + 1后，继续循环。当循环结束，返回nums[i]作为结果。
33. Search in Rotated Sorted Array
-
描述
给定一个有序数组
nums和目标数target，数组在某一位被翻转，例如：如[0, 1, 2, 3, 4] -> [3, 4, 0, 1, 2]，查找target，如果存在则返回其下标，否则返回-1。 -
题解
初始化
peak_i = -1, peak_num == -inf，代表最大值和其下标。遍历数组nums，找到最大值和其下标。此时，如果target大于peak_num，则返回-1。然后进行判断，如果target >= nums[0]，则在[0:peak_i + 1]区间进行二分查找，如果target < nums[0]，则target在翻转区间内，则在[peak_i + 1:]区间内进行二分查找。
74. Search a 2D Matrix
-
描述
给定一个二维数组
nums和一个目标数target，该二维数组的每个元素是严格按下标增长的。在二维数组nums查找元素target，如果存在则返回True，否则返回False。 -
题解
初始化
peak_j = 0，以nums[j][0] <= target为条件，遍历nums每行的第一个元素，记录peak_j = j，在区间行nums[j][:]进行二分查找，后返回结果。
240. Search a 2D Matrix II
-
描述
给定一个二维数组
nums和一个目标数target，该二维数组是的每一个行是有序的，每一列是有序的。在二维数组nums查找元素target，如果存在则返回True，否则返回False。 -
题解
初始化
peak_j = 0，以nums[j][0] <= target为条件，遍历nums每行的第一个元素，记录peak_j = j，以下标i遍历0行到j行，在区间行nums[i][:]进行二分查找，后返回结果。
252. Meeting Rooms
-
描述
给定一个数组
intervals，数组内的元素是一个整型二元组，表示了会议的开始和结束时间，如果会议时间有冲突，判断会议之间是否有冲突。 -
题解
将该数组按开始时间排序后结果记为
intervals，然后以i为下标遍历数组，如果intervals[i].start < intervals[i-1].end，则有冲突，返回False，否则继续循环直到结束，返回True，即没有冲突。
253. Meeting Rooms II
-
描述
给定一个数组
intervals，数组内的元素是一个整型的二元组，表示了会议的开始和结束时间，因为会议时间有可能冲突，返回最多需要的会议室数量。 -
题解
维护一个字典
interval_rooms_map，它的键是会议开始或结束时间，它的值时此刻会议室的“名义数量”，然后遍历intervals，对interval_rooms_map[interval.start] += 1，对interval_rooms_map[interval.end] -= 1，表示每个会议interval的起始时间对会议室的“名义数量”，即如果会议开始，那么占用数需要自增，如果结束，那么占用数自减。然后，获取该字典的所有键并升序排序，其结果记为keys_sorted。然后，初始化max_room = 0, cur_room = 0，代表最大会议室数量和当前会议室数量，通过key_sorted的key遍历interval_rooms_map的值，并使得cur_room += interval_rooms_map[key]，同时更新最大会议室数量max_room = max(max_room, cur_room)，最后返回max_room。
56. Merge Intervals
-
描述
给定一个数组
intervals，数组内的元素是一个整型的二元组，表示了开始和结束时间，由于时间可能重叠，返回合并后的intervals数组，例如：[[1, 3], [2, 6], [8, 10]]合并后应该为[[1, 6], [8, 10]。 -
题解
首先以
interval.start排序intervals数组，然后初始化结果数组results = [intervals[0]]，从下标为1开始遍历排序后的intervals数组，如果interval.start <= results[-1].end，即说明出现重叠，则results[-1].end = max(interval.end, results[-1].end)。否则，添加新合并区间results.append(interval)，最后返回结果。
动态规划 - Dynamic Programming
121. Best Time to Buy and Sell Stock
-
描述
给定一个数组
prices，数组内每个元素代表了某个股票某时刻的价格，选择一个时间买入，一个时间卖出，返回最大的收益。 -
题解
初始化最大收益
s_max=0，最小价格p_min=-inf，遍历prices中的每个价格price，取p_min = min(price, p_min)，然后计算当前买入价格收益profit = price - p_min，选择更新最大收益s_max=max(profit, s_max)，最后返回s_max作为结果。
53. Maximum Subarray
-
描述
给定一个整型数组
nums，返回最大的子数组的和。 -
题解
初始化
dp = [0] * len(nums)，以下标i遍历数组nums，则dp[i] = max(nums[i], nums[i] + dp[i - 1])，即以下标为i截止的子数组nums[:i+1]，它的最大dp[i] = max(num, num + dp[i - 1])其中dp[i]为第i个下标的最大子数组和。
70. Climbing Stairs
-
描述
给定一个
n阶楼梯，一次可以爬1阶楼梯或者2阶楼梯，返回爬到n阶，有多少种爬法。 -
题解
初始化
dp = [0] * (n + 1)，dp[i]表示爬到第i阶，有多少种爬法，所以，可以写出递推式：dp[i] = dp[i - 1] + dp[i - 2]，最后，返回dp[n - 1]作为结果。
198. House Robber
-
描述
给定一个数组
nums，nums中每个下标i对应的nums[i]代表i位置财产的价值。限定不可以同时拿取两个相邻位置的财产，返回可拿取财产的最大值。 -
题解
初始化
dp = [0] * len(nums)，则有初始情况dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])，dp[i]代表了当财产个数为i个时，可拿取财产的最大值，所以，可以写出递推式：dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])，最后返回max(dp[-1], dp[-2])作为结果。
152. Maximum Product Subarray
-
描述
给定一个整型数组
nums，返回最大的子数组的积。 -
题解
初始化
dp = [0] * len(nums)，dp[i]表示以nums[i]为最后一个元素的子数组的最大子数组的积。由于负数的存在，需要初始化dp_min = [0] * len(nums)和dp_max = [0] * len(nums)，dp_min[i]与dp_max[i]分别代表以nums[i]为最后一个元素的子数组的最小数组积和最大数组积。dp_min的意义在于，由于负数的存在，如果dp_min[i - 1]是一个负数，而nums[i]同样是一个负数，则dp_min[i - 1] * nums[i]将会是正数。所以我们可以写出递推式：dp[i] = max(dp_min[i-1] * nums[i], dp_max[i-1] * nums[i], nums[i])，然后更新dp_max[i] = dp[i]，dp_min[i] = min(dp_min[i-1] * nums[i], dp_max[i-1] * nums[i], nums[i])，最后返回max(dp)作为结果。
139. Word Break
-
描述
给定一个字符串
s，给定一个字符串数组wordDic，其元素是一些单词。如果s能被wordDic中的单词组合而成，则返回True，否则返回False。 -
题解
初始化
dp = [False] * len(s) + 1，dp[i]表示以s[i]结尾的子串，是否能被wordDic中的单词组合。则外循环以下标i遍历字符串s，内循环以下标j遍历i到len(s)，如果dp[i]为真，即以s[i]结尾的子串可以被wordDic中的单词组合，而且子串s[i: j+1]在wordDic中，那么dp[j + 1] = Ture，最后，返回dp[-1]作为结果。
62. Unique Paths
-
描述
给定一个二维数组的行列
m, n，从位置mat[0][0]出发，到达mat[-1][-1]，限定能向右或者向下移动，返回走法的总数。 -
题解
初始化
dp = [[1 for _ in range(0, n)] for _ in range(0, m)]，dp[i][j]表示从出发点mat[0][0]到该点的走法数量。则以下标i, j遍历行列，则可以写出递推式：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，最后返回dp[-1][-1]作为结果。