File tree Expand file tree Collapse file tree 1 file changed +2
-2
lines changed
problems/318. Maximum Product of Word Lengths Expand file tree Collapse file tree 1 file changed +2
-2
lines changed Original file line number Diff line number Diff line change @@ -40,7 +40,7 @@ class Solution {
40
40
- 时间复杂度:$O(n^4)$
41
41
- 空间复杂度:$O(1)$
42
42
43
- 这个算法在LeetCode提交的时候出现了超时,这个算法的时间复杂度为$O(n^4)$,显然需要优化。优化的角度在哪里呢?我们的算法中` containsCL() ` 的复杂度是$O(n^2)$,需要被执行$O(n^2)$次,所有我们优化的角度要么在 ` containsCL() ` 这个子算法中,要么在操作执行次数上。我们发现,要求出两个字符串长度乘积的最大值,那么二重循环可能避免不了,所以我们把注意力放在判断两个字符串是否有公共的字符的子算法中!
43
+ 这个算法在LeetCode提交的时候出现了超时,这个算法的时间复杂度为$O(n^4)$,显然需要优化。优化的角度在哪里呢?我们的算法中` containsCL() ` 的复杂度是$O(n^2)$,需要被执行$O(n^2)$次,所以我们优化的角度要么在 ` containsCL() ` 这个子算法中,要么在操作执行次数上。我们发现,要求出两个字符串长度乘积的最大值,那么二重循环可能避免不了,所以我们把注意力放在判断两个字符串是否有公共的字符的子算法中!
44
44
45
45
那么要判断两个字符串是否有公共的字符,怎么也要遍历每个字符吧,这样也避免不了二重循环的!!那么怎么优化呢?这时候我们想办法去构造一个新的数据结构,想办法做到在初始化和操作之间做权衡!我们希望containsCL()是借助一个新的数据结构来求解的,求解时的时间复杂度能达到O(1),把` O(n^2) ` 的时间复杂度转化到构造这个新的数据结构上!
46
46
@@ -53,7 +53,7 @@ class Solution {
53
53
54
54
![ bitmap原理] ( http://p6sh0jwf6.bkt.clouddn.com/2018-04-12-112850.jpg )
55
55
56
- 现在的主要问题是,如果构造这个位图。想法是这样的,我们利用` current_char - 'a' ` 的值来判断当前字符是哪个字符,并利用该差值来存储这个字符 :
56
+ 现在的主要问题是,如果构造这个位图。想法是这样的,我们利用` current_char - 'a' ` 的值来判断当前字符是哪个字符,并利用该差值确定存储该字符的位置 :
57
57
58
58
- ` 'a' - 'a' = 0 ` 所以,a会放到第0位,对应的从右往左的移位数为0;
59
59
- ` 'b' - 'a' = 1 ` 所以,b会放到第1位,对应的从右往左的移位数为1;
You can’t perform that action at this time.
0 commit comments