LeetCode - Algorithms - 14. Longest Common Prefix

此题在LeetCode上难度标为Easy，LintCode上却标为Medium

这题虽然不能脱离IDE直接刷题，但没怎么被卡住，一天之内就做完了，还算简单吧。有共同前缀的字符串，它们的首字母肯定一样。

JavaScript

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
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
	  var lcp = "";
	  if (strs==null || strs.length==0)
		  return lcp;
	  var minLen = strs[0].length;
	  var idx = 0;
	  for(var i=1;i<strs.length;i++) {
	    if (strs[i].length<minLen) {
		  minLen = strs[i].length;
		  idx = i;
		}
	  }
	  var lcp = "";
	  var ch = strs[idx].charAt(0);
	  var b = true;
	  for(var i=0;i<strs.length;i++) {
		  b = b && strs[i].charAt(0)==ch?true:false;
	  }
	  if (b) {
		  lcp+=ch;
		  for(var j=1;j<minLen;j++) {
			    ch = strs[idx].charAt(j);
				b = true;
			    for(var i=0;i<strs.length;i++) {
				    b = b && (strs[i].charAt(j)==ch?true:false);
				}
				if (b)
				  lcp += ch;
			  }	  
	  }
	  return lcp;    
};

Submission Detail

  • 118 / 118 test cases passed.
  • Your runtime beats 81.84 % of javascript submissions.

如果在

1
2
if (b)
  lcp += ch;

后面加个break语句用于跳出循环判断，改成

1
2
3
4
if (b)
  lcp += ch;
else
  break;

性能倒反降低了，这个有点不明白？

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
class Solution {
    public String longestCommonPrefix(String[] strs) {
    	if (strs==null || strs.length==0) return "";
    	int minStrLen = strs[0].length();
    	int idx = 0;
    	for(int i=1;i<strs.length;i++) {
    		if (strs[i].length()<minStrLen) {
    			minStrLen = strs[i].length();
    			idx = i;
    		}
    	}
    	StringBuilder lcp = new StringBuilder();
    	if (strs[idx]!=null && strs[idx].length()>0) {
        	char ch = strs[idx].charAt(0);
        	boolean b = true;
        	for(int i=0;i<strs.length;i++) {
        		b = b && (strs[i].charAt(0)==ch?true:false);
        	}
        	if (b) {
        		lcp.append(ch);
        		for(int j=1;j<minStrLen;j++) {
        			ch = strs[idx].charAt(j);
        			b = true;
        			for(int i=0;i<strs.length;i++) {
        				b = b && (strs[i].charAt(j)==ch?true:false);
        			}
        			if (b) {
        				lcp.append(ch);
        			}
        			else {
        				break;
        			}
        		}
        	}    		
    	}
        return lcp.toString();        
    }
}

Submission Detail

  • 118 / 118 test cases passed.
  • Your runtime beats 11.84 % of java submissions.

跟js代码的情况一样，加了跳出循环判断的break语句

1
2
3
4
5
6
if (b) {
  lcp.append(ch);
}
else {
  break;
}

性能倒反降低，不解？