#14.Longest Common Prefix
Problem statement
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: strs = ["flower","flow","flight"]
Output: "fl"
Example 2
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Explanation
找出陣列中所有元素最長的相同字符並返回,如果沒有相同字符則返回空字串 ""
。
例如 cat
和 carry
相同的前綴字符為 ca
Solution
用雙迴圈逐一比對,第一層遍歷元素長度,第二層則遍歷陣列內所有元素。
但是找尋陣列內元素時,不可使用超出元素長度的索引,故先找到陣列內最短長度的元素,再以此長度作為第一層迴圈的中止值。
public string LongestCommonPrefix(string[] strs)
{
if (strs.Length == 0) return null;
string res = string.Empty;
string str = strs[0];
foreach (var s in strs)
{
if (s.Length < str.Length)
str = s;
}
int len = strs.Length;
for (int i = 0; i < str.Length; i++)
{
for (int j = 0; j < len; j++)
{
if (str[i] == strs[j][i])
continue;
else
return res;
}
res += str[i];
}
return res;
}
Reference
Thanks for reading the article 🌷 🌻 🌼
If you like it, please don't hesitate to click heart button ❤️
or click like on my Leetcode solution
or follow my GitHub ⭐
or buy me a coffee ⬇️ I'd appreciate it.
Top comments (0)