开发者社区云计算文章正文

[LeetCode] Longest Common Prefix

2015-07-12 831

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Use the strs[0] as the reference string and then compare it with the remaining strings from left to right.

Use the strs[0] as the reference string and then compare it with the remaining strings from left to right. Once we find a string with length less than strs[0] or different letters in the corresponding position, we cannot move on and should return the longest common prefix string lcp. Each time we finish checking a position and have not returned, we add the letter at that position to lcp.

 1 class Solution {
 2 public:
 3     string longestCommonPrefix(vector<string>& strs) {
 4         if (strs.empty()) return "";
 5         string lcp = "";
 6         int m = strs.size(), n = strs[0].length();
 7         for (int i = 0; i < n; i++) {
 8             for (int j = 1; j < m; j++)
 9                 if (strs[j].length() == i || strs[j][i] != strs[0][i])
10                     return lcp;
11             lcp += strs[0][i];
12         }
13         return lcp;
14     }
15 };

关键词：

LeetCode longest

LeetCode longest common prefix

LeetCode prefix

jianchao_li

xindoo

8月前

Leetcode 516. Longest Palindromic Subsequence

找到一个字符串的最长回文子序列，这里注意回文子串和回文序列的区别。子序列不要求连续，子串（substring）是要求连续的。leetcode 5. Longest Palindromic Substring就是求连续子串的。

xindoo

31 0 0

xindoo

8月前

Java

Leetcode 3. Longest Substring Without Repeating Characters

此题题意是找出一个不包含相同字母的最长子串，题目给出了两个例子来说明题意，但这两个例子具有误导性，让你误以为字符串中只有小写字母。还好我是心机boy，我把大写字母的情况也给考虑进去了，不过。。。。字符串里竟然有特殊字符，于是贡献了一次wrong answer，这次我把ascii字符表都考虑进去，然后就没问题了。这个故事告诫我们在编程处理问题的时候一定要注意输入数据的范围，面试中可以和面试官去确认数据范围，也能显得你比较严谨。

xindoo

36 3 3

ruicore

LeetCode 424. Longest Repeating Character Replacem

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

ruicore

86 0 0