4

Find the longest common prefix in an array of strings (Longest Common Prefix) |...

 2 years ago
source link: https://tianrunhe.wordpress.com/2012/07/29/find-the-longest-common-prefix-in-an-array-of-strings-longest-common-prefix/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Find the longest common prefix in an array of strings (Longest Common Prefix)

29 Jul 2012 1 Comment

by Runhe Tian in LeetCode Tags: Array, C++, Java, String

Write a function to find the longest common prefix string amongst an array of strings.

Thoughts:
Apparently this can be done in O(n). We start with the first string as the longest common prefix. We then go through every string in the array and compare the prefix with them. Update (shorten) the prefix if needed.

Code (Java):

public class Solution {
public String longestCommonPrefix(String[] strs) {
String prefix = new String();
if(strs.length > 0)
prefix = strs[0];
for(int i = 1; i < strs.length; ++i) {
String s = strs[i];
int j = 0;
for(; j < Math.min(prefix.length(), s.length()); ++j) {
if(prefix.charAt(j) != s.charAt(j)) {
break;
}
}
prefix = prefix.substring(0, j);
}
return prefix;
}
}

Code (C++):

class Solution {
public:
string longestCommonPrefix(vector<string> &strs) {
string prefix;
if(strs.size() > 0)
prefix = strs[0];
for(int i = 1; i < strs.size(); ++i) {
string s = strs[i];
int j = 0;
for(; j < min(prefix.size(), s.size()); ++j) {
if(prefix[j] != s[j])
break;
}
prefix = prefix.substr(0, j);
}
return prefix;
}
};

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK