C# 写 LeetCode easy #14 Longest Common Prefix
程序员文章站
2022-08-09 10:42:33
14、Longest Common Prefix Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return a ......
14、longest common prefix
write a function to find the longest common prefix string amongst an array of strings.
if there is no common prefix, return an empty string ""
.
example 1:
input: ["flower","flow","flight"] output: "fl"
example 2:
input: ["dog","racecar","car"] output: "" explanation: there is no common prefix among the input strings.
note:
all given inputs are in lowercase letters a-z
.
代码:
static void main(string[] args) { string[] str = new string[] { "my","myname","mys"}; string res=getlongestcommonprefix(str); console.writeline(res); console.readkey(); } private static string getlongestcommonprefix(string[] strs) { if (strs.length == 0) return ""; if (strs.length == 1) return strs[0]; var min = int.maxvalue; foreach (var item in strs) { if (item.length < min) { min = item.length; } } var index = -1; for (int i=0; i < min; i++) { for (int j = 1; j < strs.length; j++) { if (strs[j][i] != strs[0][i]) { return strs[0].substring(0, i); } else { index = i; } } } return strs[0].substring(0,index+1); }
解析:
输入:字符串数组
输出:字符串
思想:
首先,分三部分,当数组为空时,返回空字符串;数组中只有一个元素,输出该元素;数组中有若干字符串,则进行以下操作。(注意:这里也可以判断数组中是否含有空字符串,有则返回空)
其次,对于一般情况,先找出数组中最小长度的字符串,根据这个长度,从第一个字符开始遍历。
最后,将数组中的每个字符串和第一个字符串的每个字符进行比较。相同则记录字符索引值,否则返回共同子串。
时间复杂度:o(m*n) 其中m是单词最大长度,n是数组长度。
上一篇: MySQL查询语句实操练习
下一篇: jQuery获取或设置元素的宽度和高度