【最长公共前缀】算法优化笔记

不念不忘少年蓝@ 2023-06-30 08:38 11阅读 0赞

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

示例 1:
    
    	输入: ["flower","flow","flight"]
    	输出: "fl"
    	示例 2:
    
    	输入: ["dog","racecar","car"]
    	输出: ""
    	解释: 输入不存在公共前缀。

> *来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-common-prefix*

##### 初步分析 #####

1.  暴力循环嵌套比较得出最长前缀
2.  取第一个string为原值，逐步比较缩短得到最长公共前缀。

# 详细代码 #

###### 缩减法 ######

public class Solution { 
        public string LongestCommonPrefix(string[] strs) { 
            if(strs.Length==0) return "";
            string strpublic = strs[0];
            for(int i=0;i<strs.Length;i++)
            { 
                while(strs[i].IndexOf(strpublic)!=0)
                { 
                    strpublic=strpublic.Substring(0, strpublic.Length - 1);
                }
            }
            return strpublic;
        }
    }

###### 个人暴力法 ######

public class Solution { 
        public string LongestCommonPrefix(string[] strs) { 
            if (strs.Length <= 0) return "";
                string sum="";
                for (int i = 0; i < strs[0].Length; i++)
                { 
                    if (IsIndexEqual(strs, i) == "")
                        return sum;
                    else
                    sum += IsIndexEqual(strs, i);
    
                }
                return sum;
        }
    
            public string IsIndexEqual(string[] strs,int index) { 
                 for (int i = 0; i < strs.Length; i++)
                { 
                    if (index >= strs[i].Length)
                        return "";
                }
    
    
                char before = strs[0][index];
                int isit=1;
                for (int i = 0; i < strs.Length; i++)
                { 
                    if (before == strs[i][index])
                        isit &= 1;
                    else
                        isit &= 0;
                }
                if (isit == 1)
                    return before.ToString();
                else
                    return "";
        }
    }