神刀安全网

C++ Coding Exercise – Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings. For example, [“aa”, “a”] should return “a”. The common prefix length should not exceed the minimal string length in the vector. And all we need to do is to check each character from the start to see if they appear in all strings. Return the substring if any mis-match found.

This is a O(MN) solution that M is the least number of the string length and N is the number of strings in the array.

class Solution { public:     string longestCommonPrefix(vector<string>& strs) {         int n = INT_MAX;         if (strs.size() <= 0) {             return "";         }         if (strs.size() == 1) {             return strs[0];         }         // get the min length         for (int i = 0; i < strs.size(); i ++) {             n = strs[i].length() < n ? strs[i].length() : n ;         }         for (int i = 0; i < n; i ++) { // check each character             for (int j = 1; j < strs.size(); j ++) {                 if (strs[j][i] != strs[j - 1][i]) { // we find a mis-match                     return strs[0].substr(0, i);                 }             }         }         // prefix is n-length         return strs[0].substr(0, n);     } };
class Solution { public:     string longestCommonPrefix(vector<string>& strs) {         int n = INT_MAX;         if (strs.size() <= 0) {             return "";         }         if (strs.size() == 1) {             return strs[0];         }         // get the min length         for (int i = 0; i < strs.size(); i ++) {             n = strs[i].length() < n ? strs[i].length() : n ;         }         for (int i = 0; i < n; i ++) { // check each character             for (int j = 1; j < strs.size(); j ++) {                 if (strs[j][i] != strs[j - 1][i]) { // we find a mis-match                     return strs[0].substr(0, i);                 }             }         }         // prefix is n-length         return strs[0].substr(0, n);     } };

–EOF–

GD Star Rating

loading…

206 words

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » C++ Coding Exercise – Longest Common Prefix

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址