This is the 15th day of my participation in the genwen Challenge
Topic describes
Write a function to find the longest public prefix in an array of strings.
Returns the empty string “” if no public prefix exists.
Example 1:
STRS = ["flower","flow","flight"]Copy the code
Example 2:
Input: STRS = ["dog","racecar","car"] Output: "" Explanation: The input does not have a common prefix.Copy the code
Tip:
- 0 < =
strs.length
< = 200 - 0 < =
strs[i].length
< = 200 strs[i]
Contains only lowercase English letters
Their thinking
Solution 1: Python feature, take each word in the same position of the letter, see if the same
class Solution:
def longestCommonPrefix(self, strs) :
""" :type strs: List[str] :rtype: str """
res = ""
for tmp in zip(*strs):
tmp_set = set(tmp)
if len(tmp_set) == 1:
res += tmp[0]
else:
break
return res
Copy the code
Solution two: take a word s and compare it with the next word to see how long s has the same prefix as each word. Walk through all the words.
class Solution:
def longestCommonPrefix(self, s: List[str]) - >str:
if not s:
return ""
res = s[0]
i = 1
while i < len(s):
whiles[i].find(res) ! =0:
res = res[0:len(res)-1]
i += 1
return res
Copy the code
Solution three sort the array lexicographically and compare how many prefixes the first and last word have the same
class Solution:
def longestCommonPrefix(self, s: List[str]) - >str:
if not s:
return ""
s.sort()
n = len(s)
a = s[0]
b = s[n-1]
res = ""
for i in range(len(a)):
if i < len(b) and a[i] == b[i]:
res += a[i]
else:
break
return res
Copy the code
C++ version if no string, return empty string; If there is only one string, return it.
Otherwise, for each character of STRS [0], compare the rest of the string one by one. If it finds any that are not long enough, or that the characters do not match, it ends there and returns the substring that has been compared so far.
If all STRS [0] characters are compared, return itself.
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.size() = =0)
return "";
if (strs.size() = =1)
return strs[0];
for (int length = 0; length < strs[0].size(a); ++length)for (int i = 1; i < strs.size(a); ++i)if (length == strs[i].size() || strs[i][length] ! = strs[0][length])
return strs[0].substr(0, length);
return strs[0]; }};Copy the code