[转][LeetCode]Longest Common Prefix ——求字符串的最长公共前缀

题记：

这道题不难但是很有意思，有两种解题思路，可以说一种是横向扫描，一种是纵向扫描。

横向扫描：遍历所有字符串，每次跟当前得出的最长公共前缀串进行对比，不断修正，最后得出最长公共前缀串。

纵向扫描：对所有串，从字符串第0位开始比较，全部相等则继续比较第1,2...n位，直到发生不全部相等的情况，则得出最长公共前缀串。

横向扫描算法实现：

//LeetCode_Longest Common Prefix

//Written by zhou

//2013.11.22

class Solution {

public:

    string longestCommonPrefix(vector<string> &strs) {

        // IMPORTANT: Please reset any member data you declared, as

        // the same Solution instance will be reused for each test case.

        if (strs.size() == )

          return "";

        string prefix = strs[];

        for (int i = ; i < strs.size(); ++i)

        {

            if (prefix.length() ==  || strs[i].length() == )

               return "";

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

            int j;

            for (j = ; j < len; ++j)

            {

                if (prefix[j] != strs[i][j])

                    break;

            }

            prefix = prefix.substr(,j);

        }

        return prefix;

    }

};

纵向扫描代码实现：

function longestCommonPrefix(strs:Array):String{

    if(strs == null || strs.length == 0)return;

    for(i:int = 0; i < str[0].length - 1; i++)

    {

        for(j:int = 0; j < str.length - 1; j++)

        {

            if(str[i].charAt(j) != str[0].charAt(j))return strs[0].substr(0,j);

        }

    }

    return strs[0];

}