leetcode筆記：Longest Common Prefix

leetcode筆記：Longest Common Prefix

一. 題目描述

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

二. 題目分析

題目的大意是，給定一組字符串，找出所有字符串的最長公共前綴。

對比兩個字符串的最長公共前綴，其前綴的長度肯定不會超過兩個字符串中較短的長度，設最短的字符串長度為n，那麼只要比較這兩個字符串的前n個字符即可。

使用變量prefix保存兩個字符串的最長公共前綴，再將prefix作為一個新的字符串與數組中的下一個字符串比較，以此類推。
一個特殊情況是，若數組中的某個字符串長度為0，或者求得的當前最長公共前綴的長度為0，就直接返回空字符串。

三. 示例代碼

#include 
#include 
#include 
using namespace std;

class Solution {
public:
    string longestCommonPrefix(vector &strs) 
    {
        if (strs.size() == 0)
          return ;

        string prefix = strs[0];
        for (int i = 1; i < strs.size(); ++i)
        {
            if (prefix.length() == 0 || strs[i].length() == 0)
               return ;

            int len = prefix.length() < strs[i].length() ? prefix.length() : strs[i].length();

            int j;     
            for (j = 0; j < len; ++j)
            {
                if (prefix[j] != strs[i][j])
                    break;
            }
            prefix = prefix.substr(0,j);
        }
        return prefix;
    }
};

四. 小結

該題思路不難，而且還有幾種相似的解決思路，在實現時需要做到盡量減少比較字符的操作次數。