关于最长公共子序列的基础实现

发表于 |

问题描述

  • 写一个function，输入两个字符串序列（wordA, wordB），查找他们最长公共子序列并输出。
  • 例如 wordA = ‘abcdde’, wordB = ‘bcdff’。输出：’bcd’。

思路分析

没有哪个问题是两个for循环解决不了的，如果有那就三个。

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
// 三个for循环
function maxSub(wordA, wordB) {
	let lenA = wordA.length;
	let lenB = wordB.length;
	if (lenA > lenB) {
		let temp = wordA;
		wordA = wordB;
		wordB = temp;
		temp = lenA;
		lenA = lenB;
		lenB = temp;
	}
	let maxSubStr = '';
	for (let i = 0; i < lenA; i++) {
		for (l = 1; l <= lenA - i; l++) {
			let subStrA = wordA.slice(i, i + l);
			for (let j = 0; j < lenB; j++) {
				let subStrB = wordB.slice(j, j + l)
				if (subStrA === subStrB && l > maxSubStr.length) {
					maxSubStr = subStrA;
				}
			}
		}
	}
	return maxSubStr;
}

function genRandStr(n) {
	let charArr = 'ABCDEFGHJKMNPQRSTWXYZabcdefhijkmnprstwxyz2345678';
	let charLen = charArr.length;
	let randStr = '';
	for (i = 0; i < n; i++) {
		randStr += charArr.charAt(Math.floor(Math.random() * charLen));
	}
	return randStr;
}

function testFunc(n) {
	let wordA = genRandStr(n);
	let wordB = genRandStr(n);
	let startTime = Date.now();
	let result = lcs(wordA, wordB);
	let endTime = Date.now();
	console.log(result, endTime - startTime);
}

// 两个for循环
function lcs(word1, word2) {
  var max = 0;
  var index = 0;
  var lcsarr = new Array(word1.length + 1);
    for (var i = 0; i <= word1.length + 1; ++i) {
      lcsarr[i] = new Array(word2.length + 1);
      for (var j = 0; j <= word2.length + 1; ++j) {
        lcsarr[i][j] = 0;
      }
    }
    for (var i = 1; i <= word1.length; ++i) {
      for (var j = 1; j <= word2.length; ++j) {
        if (word1[i - 1] == word2[j - 1]) {
          lcsarr[i][j] = lcsarr[i - 1][j - 1] + 1;
        } else {
          lcsarr[i][j] = 0;
        }
        if (max < lcsarr[i][j]) {
          max = lcsarr[i][j];
          index = i;
        }
      }
    }
    var str = "";
    if (max == 0) {
      return "";
    } else {
      for (var i = index - max; i < index; ++i) {
        str += word1[i];
      }
    return str;
    }
}

经过实测，maxStr方法在计算长度为1000的字符串时，需要的时间为10s以上，而lcs方法在计算1000长度的字符串时，耗时在20毫秒级别，而在10000长度时，耗时3s左右。

关于优化（空间换时间）

所有针对时间上的优化，都可以归为用空间换时间，三个for循环的方法，虽然耗时长，但是中间环节不生成多余的数据。两个for循环的优化算法，虽然时间上短了，但是计算过程中，需要一个lcsarr二维数组，来存储计算过程中生成的每一个值，然后保存起来，以便后续查找使用。

这和平时用过的缓存思想极其相似，拿斐波那契数列来举例，常规的做法是通过递归调用，但是耗时会很长，如果在递归的过程中假如cache数组缓存，可以明显提高时间，但是多出来cache存储空间就是换取时间的代价。

这里我们顺便考虑下排序算法，初级排序（冒泡，插入，选择）时间复杂度为O(n^2)，高级排序算法（希尔，堆排序，快速）时间复杂度O(nlogn)，在不引入额外空间的条件下（事实上也没有额外办法引入），排序的时间复杂度最多限制在了nlogn这个数量级，之所以能从n^2缩减到n*logn也是因为在自身数组空间的基础上，充分利用了自身空间做的一个数据交换（比如快速排序，在自己内部通过二分法，每次处理一半数据）达到了时间上的缩减。