2019-03-5-算法-进化（最长公共前缀）

川长思鸟来 2022-03-12 03:39 69阅读 0赞

**题目描述**  
编写一个函数来查找字符串数组中的最长公共前缀。  
如果不存在公共前缀，返回空字符串 “”。

**示例 1:**

输入: ["flower","flow","flight"]
    输出: "fl"

**示例 2:**

输入: ["dog","racecar","car"]
    输出: ""
    解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。

我的初版解决思路为遍历数组，挨个字符进行比较，直到结束。代码如下：

//循环遍历，有两种退出条件: 1,数组最短元素  2,数组内String相同位置字符不同
    	public String longestCommonPrefix(String[] strs) {
    		if(strs == null || strs.length ==0) {
    			return "";
    		}
            StringBuilder sb = new StringBuilder();
            boolean toEnd = false;
    		for(int i=0;;i++) {
    			if(toEnd) {
    				break;
    			}
    			
    			for(String arr:strs) {
    				if(i >= arr.length()) {
    					//1,数组最短元素
    					if(sb.length()>i) {
    						sb.deleteCharAt(i);
    					}
    					toEnd =true;
    					break;
    				}
    				if(sb.length()<=i) {
    					sb.append(arr.charAt(i));
    				}else if(sb.charAt(i) != arr.charAt(i)) {
    					//2,数组内String相同位置字符不同
    					sb.deleteCharAt(i);
    					toEnd =true;
    					break;
    				}
    				
    			}
    		}
    		
    		return sb.toString();
        }

采用水平扫描法进行优化  
![优化思路][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nX2Jv_size_16_color_FFFFFF_t_70]  
举例：  
![例子][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nX2Jv_size_16_color_FFFFFF_t_70 1]  
最终优化代码如下：

public String longestCommonPrefix(String[] strs) {
    		if(strs == null || strs.length ==0) {
    			return "";
    		}
            String prefix = strs[0];
            for(int i=0;i<strs.length;i++) {
            	while(strs[i].indexOf(prefix) != 0) {
            		prefix = prefix.substring(0, prefix.length()-1);
            		if(prefix.isEmpty()) {
            			return "";
            		}
            	}
            }
            return prefix;
        }

代码简洁清晰了很多。  
持续精进，加油！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nX2Jv_size_16_color_FFFFFF_t_70]: /images/20220312/3137696c9a744f1c8bde9e8164cac286.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nX2Jv_size_16_color_FFFFFF_t_70 1]: /images/20220312/44250e6e0bfb403580380293aa72911e.png