-
Notifications
You must be signed in to change notification settings - Fork 0
/
leetcode14 最长公共前缀
160 lines (151 loc) · 5.2 KB
/
leetcode14 最长公共前缀
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例:
输入: ["flower","flow","flight"]
输出: "fl"
代码示意:
一、横向扫描:从前往后依次比较字符串,获取最长公共前缀
时间复杂度:O(mn) m-字符串平均长度(字符数) n-字符串数目 空间复杂度O(1)
var longestCommonPrefix = function(strs) {
if(strs.length<2) return strs.join();
let ans = strs.reduce((prev,str)=>{
let i=0;
for(;i<prev.length && i<str.length;i++){
if(prev.charAt(i)!==str.charAt(i)) prev = prev.substring(0,i);
}
prev = prev.substring(0,i);
return prev;
})
return ans;
}
二、纵向扫描:将字符串一个个的竖向排列,按照字符一列列的比较,直至不相同,返回前n列表示的最长公共前缀
时间复杂度:O(mn) 空间复杂度O(1)
var longestCommonPrefix = function(strs) {
if(strs.length<2) return strs.join();
let prev = strs[0];
for(let i=1;i<strs.length;i++){
let j=0;
for(;j<prev.length && j<strs[i].length;j++){
if(prev.charAt(j)!==strs[i].charAt(j)){
prev = prev.substring(0,j);
}
}
prev = prev.substring(0,j);
}
return prev;
}
三、分治思想:lcp(str1,str2...strn)=lcp(lcp(str1,str2...strk),lcp(strk+1,...strn))
时间复杂度O(mn) 空间复杂度O(mlogn)
var longestCommonPrefix = function(strs) {
if(strs.length<2) return strs.join();
let prefix = lcp(strs,0,strs.length-1);
return prefix;
}
var lcp = function(strs,start,end){
if(start === end) return strs[start];
let mid = start + Math.floor((end-start)/2);
let left_common = lcp(strs,start,mid);
let right_common= lcp(strs,mid+1,end);
let common,i=0;
for(;i<left_common.length && i< right_common.length;i++){
if(left_common.charAt(i)!==right_common.charAt(i)){
common = left_common.substring(0,i);
break;
}
}
common = left_common.substring(0,i);
return common;
}
四、双指针:最长公共前缀的长度一定小于等于最短字符串长度 取最短长度的中间mid来匹配前0~mid的字符 全部匹配 则扩大匹配范围 否则缩小匹配范围 -->性能表现最好 时间复杂度第二低 空间复杂度最低
时间复杂度O(mnlogm) 空间复杂度O(1)
var longestCommonPrefix = function(strs) {
if(strs.length<2) return strs.join();
let minLen = strs[0].length;
for(const str of strs){
minLen = Math.min(minLen,str.length);
}
let left=0,right=minLen-1,mid;
while(left <= right){
mid = left + Math.floor((right-left)/2);
if(isCommonPrefix(strs,mid)){
left = mid+1;
}else {
right = mid-1;
}
}
return strs[0].substring(0,left);
}
var isCommonPrefix = function(strs,len){
let prev = strs[0];
for(let i=1;i<strs.length;i++){
for(let j=0;j<=len;j++){
if(prev.charAt(j)!==strs[i].charAt(j)){
return false;
}
}
}
return true;
}
五、排序+比较最大最小字符串:遍历一次数组得到最大最小字符串 两者的最长公共前缀就是所有字符串的公共前缀 --> 性能表现次之 时间复杂度最低
时间复杂度:O(n+m) 空间复杂度:O(1)
var longestCommonPrefix = function(strs) {
if(strs.length<2) return strs.join();
let minStr = strs[0],maxStr=strs[0];
for(const str of strs){
minStr = str < minStr? str : minStr;
// minStr = Math.min(minStr,str);——>null 注意Math.min Math.max 不适用于字符串值大小的比较
maxStr = str > maxStr? str : maxStr;
}
for(let i=0;i<minStr.length;i++){
if(minStr.charAt(i)!==maxStr.charAt(i)){
return minStr.substring(0,i);
}
}
return minStr;
}
六、字典树
时间复杂度O(s+m) 空间复杂度O(s)-->s表示所有字符数目 m表示最长公共前缀的长度
var longestCommonPrefix = function(strs) {
if(strs.length<2) return strs.join();
let trie = new Trie();
for(const str of strs){
if(!trie.insert(str)) return "";
}
return trie.searchLPC();
}
//构造 字典树节点 节点只包含两部分next、isEnd 字符的值作为节点的key
var TrieNode = function(){
this.next = {}; //子节点集合
this.isEnd = false; //当前节点是否是某一字符串的末尾字符
}
//构造 字典树
var Trie = function(){
this.root = new TrieNode();
}
//为字典树原型上添加方法
Trie.prototype.insert=function(word){
if(!word) return false;
let node = this.root;
for(let i in word){
if(!node.next[word[i]]){
node.next[word[i]] = new TrieNode();
}
node = node.next[word[i]];
}
node.isEnd = true;
return true;
}
Trie.prototype.searchLPC = function(){
let node = this.root,prev = '';
while(node.next){
let keys = Object.keys(node.next);
if(keys.length!==1) break;
if(node.next[keys[0]].isEnd){
prev += keys[0];
break;
}
prev += keys[0];
node = node.next[keys[0]];
}
return prev;
}