LeetCode - 14. Longest Common Prefix

简介: 14. Longest Common Prefix Problem's Link  ---------------------------------------------------------------------------- Mean:  给定一个字符串集合,找出这个字符串集合的最长公共前缀.

 14. Longest Common Prefix

Problem's Link

 ----------------------------------------------------------------------------

Mean: 

给定一个字符串集合,找出这个字符串集合的最长公共前缀.

analyse:

直接暴力.

Time complexity: O(N)

 

view code

/**
* -----------------------------------------------------------------
* Copyright (c) 2016 crazyacking.All rights reserved.
* -----------------------------------------------------------------
*       Author: crazyacking
*       Date  : 2016-02-16-12.27
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);

class Solution
{
public :
    string longestCommonPrefix( vector < string >& strs)
    {
        string ret;
        int si = strs . size();
        if( si <= 0) return ret;
        bool flag = 0;
        for( int i = 0; i < strs [ 0 ]. length(); ++ i)
        {
            for( int j = 1; j < si; ++ j)
            {
                if( strs [ j ]. length() < i || strs [ j ][ i ] != strs [ 0 ][ i ])
                {
                    flag = 1;
                    break;
                }
            }
            if( flag) break;
            ret . push_back( strs [ 0 ][ i ]);
        }
        return ret;
    }
};

int main()
{
    Solution solution;
    int n;
    while( cin >>n)
    {
        vector < string > strs;
        while(n --)
        {
            string tmp;
            cin >> tmp;
            strs . push_back( tmp);
        }
        cout << solution . longestCommonPrefix( strs) << endl;
    }
    return 0;
}

 

目录
相关文章
Leetcode 516. Longest Palindromic Subsequence
找到一个字符串的最长回文子序列,这里注意回文子串和回文序列的区别。子序列不要求连续,子串(substring)是要求连续的。leetcode 5. Longest Palindromic Substring就是求连续子串的。
49 0
|
Java
Leetcode 3. Longest Substring Without Repeating Characters
此题题意是找出一个不包含相同字母的最长子串,题目给出了两个例子来说明题意,但这两个例子具有误导性,让你误以为字符串中只有小写字母。还好我是心机boy,我把大写字母的情况也给考虑进去了,不过。。。。字符串里竟然有特殊字符,于是贡献了一次wrong answer,这次我把ascii字符表都考虑进去,然后就没问题了。这个故事告诫我们在编程处理问题的时候一定要注意输入数据的范围,面试中可以和面试官去确认数据范围,也能显得你比较严谨。
50 3
LeetCode 424. Longest Repeating Character Replacem
给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换 k 次。在执行上述操作后,找到包含重复字母的最长子串的长度。
104 0
LeetCode 424. Longest Repeating Character Replacem
LeetCode 409. Longest Palindrome
给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。 在构造过程中,请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
74 0
LeetCode 409. Longest Palindrome
LeetCode 395. Longest Substring with At Least K
找到给定字符串(由小写字符组成)中的最长子串 T , 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。
91 0
LeetCode 395. Longest Substring with At Least K
|
Windows
LeetCode 388. Longest Absolute File Path
我们致力于寻找我们文件系统中文件的最长 (按字符的数量统计) 绝对路径。例如,在上述的第二个例子中,最长路径为 "dir/subdir2/subsubdir2/file2.ext",其长度为 32 (不包含双引号)。
83 0
LeetCode 388. Longest Absolute File Path
|
存储
LeetCode 329. Longest Increasing Path in a Matrix
给定一个整数矩阵,找出最长递增路径的长度。 对于每个单元格,你可以往上,下,左,右四个方向移动。 你不能在对角线方向上移动或移动到边界外(即不允许环绕)。
71 0
LeetCode 329. Longest Increasing Path in a Matrix
|
算法
LeetCode 300. Longest Increasing Subsequence
给定一个无序的整数数组,找到其中最长上升子序列的长度。
53 0
LeetCode 300. Longest Increasing Subsequence
|
算法
LeetCode 128. Longest Consecutive Sequence
给定一个未排序的整数数组,找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)。
88 0
LeetCode 128. Longest Consecutive Sequence
|
Java 程序员 开发者
LeetCode第三题(Longest Substring Without Repeating Characters)三部曲之三:两次优化
本文是《LeetCode第三题(Longest Substring Without Repeating Characters)三部曲》的第二篇,前一篇文章已经列出了完整的解题思路,今天来将此思路转化为具体的Java代码
103 0
LeetCode第三题(Longest Substring Without Repeating Characters)三部曲之三:两次优化