- 浏览: 19069 次
- 性别:
- 来自: 北京
文章分类
最新评论
题目描述
Write a function to find the longest common prefix string amongst an array of strings.
解题思路
本题要求找出所有字符串的公共前缀。思路是利用set的所有元素的唯一性,首先找到所有的可能子串,然后确定是否为公共子串。
相关知识点
(1)Java中的set遍历
注意:当在遍历过程中需要对set进行删除等改变set结构的时,一定要使用iterator这种方式。具体原因参见:http://fine36.blog.163.com/blog/static/189251005201258113857343/
(2)Java中的set
自己的代码
Write a function to find the longest common prefix string amongst an array of strings.
解题思路
本题要求找出所有字符串的公共前缀。思路是利用set的所有元素的唯一性,首先找到所有的可能子串,然后确定是否为公共子串。
相关知识点
(1)Java中的set遍历
1.迭代遍历: Set<String> set = new HashSet<String>(); Iterator<String> it = set.iterator(); while (it.hasNext()) { String str = it.next(); System.out.println(str); } 2.for循环遍历: for (String str : set) { System.out.println(str); }
注意:当在遍历过程中需要对set进行删除等改变set结构的时,一定要使用iterator这种方式。具体原因参见:http://fine36.blog.163.com/blog/static/189251005201258113857343/
(2)Java中的set
Set<String> set = new HashSet<String>();
自己的代码
package leetcode; import java.util.HashSet; import java.util.Iterator; import java.util.Set; public class LongestCommonPrefix { public String longestCommonPrefix(String[] strs) { Set<String> set = new HashSet<String>(); //将每个str的所有的可能添加到set中 for(int times = 0; times < strs.length; times++){ String str = strs[times]; String tempStr = ""; for(int i = 0; i < str.length(); i++){ tempStr += str.charAt(i); set.add(tempStr); } }//System.out.println(set.toString()); //判断所有str的commonPrefix Iterator<String> it = set.iterator(); while(it.hasNext()){ String commonPrefix = it.next(); for(int i = 0; i < strs.length; i++){ if(!strs[i].startsWith(commonPrefix)) { it.remove(); break; } } } //返回longestCommonPrefix if(set.size() == 0) return ""; String commonPrefix = ""; for(String s : set){ if(s.length() > commonPrefix.length()) commonPrefix = s; } return commonPrefix; } public static void main(String[] args) { String[] strs = { "abc", "abd", "akc" }; LongestCommonPrefix lcp = new LongestCommonPrefix(); System.out.println(lcp.longestCommonPrefix(strs)); } }
发表评论
-
Java中String与StringBuffer的区别
2014-10-29 21:07 297String和StringBuffer的区别,网上资料可以说 ... -
String to Integer (atoi)
2014-10-29 17:13 398题目描述 Implement atoi to convert ... -
Implement strStr()
2014-10-28 15:17 283题目描述 Implement strStr(). Retu ... -
Valid Palindrome
2014-10-23 10:32 419题目描述 Given a string, determine ... -
ZigZag Conversion
2014-10-22 19:51 340题目描述 The string "PAYPALIS ... -
Add Binary
2014-10-22 19:43 301题目描述 Given two binary strings, ... -
Count and Say
2014-10-22 19:44 346题目描述 The count-and-say sequence ... -
Valid Sudoku
2014-10-21 10:22 355题目描述 Determine if a Sudoku is v ... -
Valid Parentheses
2014-10-21 09:41 322题目描述 Given a string containing ... -
Palindrome Number
2014-10-21 09:41 344题目描述 Determine whether an integ ... -
Length of Last Word
2014-10-21 09:41 357题目描述 Given a string s consists ... -
Minimum Depth of Binary Tree
2014-10-21 09:41 307题目描述 Given a binary tree, find ... -
Remove Nth Node From End of List
2014-10-20 16:36 255题目描述 Given a linked list, remov ... -
Path Sum
2014-10-20 15:37 292题目描述 Given a binary tree and a ... -
Binary Tree Level Order Traversal II
2014-10-20 11:17 232题目描述 Given a binary tree, retur ... -
Binary Tree Level Order Traversal
2014-10-20 11:03 292题目描述 Given a binary tree, retur ... -
Pascal's Triangle II
2014-10-20 10:07 255题目描述 Given an index k, return t ... -
Pascal's Triangle
2014-10-19 12:24 317题目描述 Given numRows, generate th ... -
Plus One
2014-10-19 11:51 336题目描述 Given a non-negative numbe ... -
Merge Sorted Array
2014-10-18 10:45 397题目描述 Given two sorted integer a ...
相关推荐
LeetCode Longest Common Prefix解决方案
asks for the length of the longest common prefix between suffixes beginning at i and j. A compressed LCE data structure is a data structure that stores T in a compressed form while supporting fast LCE...
算法#26--查找字符串数组中最长的公共前缀Write a function to find the longest common prefix string
leetcode双人赛LeetCode 编号 题目 难度 题型 备注 Two Sum 简单 ...Common Prefix 简单 字串 Valid Parentheses 简单 堆叠 重要 Merge Two Sorted Lists 简单 链结串列 重要 Remove Duplicates from
Common Prefix 15. 3Sum 20. Valid Parentheses 21. Merge Two Sorted Lists 22. Generate Parentheses 25. Reverse Nodes in k-Group 26. Remove Duplicates from Sorted Array 27. Remove Element 28. Implement ...
Longest Common Prefix Valid Number Integer to Roman Roman to Integer Count and Say Anagrams Valid Anagram Simplify Path Length of Last Word Isomorphic Strings Word Pattern 栈和队列 栈 Min Stack Valid ...
leetcode Python 001 leetcode的算法问题 这是我的解决方案,用 cpp 、 java 和 python 编写 #LeetCode 解决的问题: 001. Two Sum 002. Add Two ...Longest ...Longest ...Longest Common Prefix 019. R
leetcode 2 sum c leetcode 力扣(Leetcode)编程题,JavaScript版本。...Common Prefix 简单 15 3Sum 中等 16 3Sum Closest 中等 17 Letter Combinations of a Phone Number DFS 中等 18 4Sum 中等 19 Remo
leetcode ...Common Prefix 015 3Sum 016 3Sum Closest 017 Letter Combinations of a Phone Number 018 4Sum 020 Valid Parentheses 022 Generate Parentheses 028 Implement strStr() 031 Next Permutat
第 338 章力码 LeetCode刷题总结 1.Two Sum 2.Add Two ...Common Prefix (Trie树待完成) 15.3Sum 16.3Sum Closest 17.Letter Combinations of a Phone Number 18.4Sum 19.Remove Nth Node From End
Common Prefix 最长公共前缀 20 Valid Parentheses 有效的括号 26 Remove Duplicates from Sorted Array 删除排序数组中的重复项 32 Longest Valid Parentheses 最长有效括号 33 Search in Rotated Sorted Array ...
leetcode中文版 LeetCode # Title Chinese Tag Solution ...Common Prefix 最长公共前缀 string 16 3Sum Closest 最接近的三数之和 two pointers,array 21 Merge Two Sorted Lists 合并两个有序链表 lin
Common Prefix 15 Three Sum 16 Three Sum Closest 20 Valid Parentheses 26 Remove Duplicates from Sorted Array 48 Rotate Image 53 Maximum Subarray 55 Jump Game 56 Merge Intervals 64 Minimum Path Sum 73
lru cache leetcode #算法解题报告 主要记录我每天做的题目,包括leetcode, ...Common Prefix 15.3Sum 16.3Sum Closest 19.Remove Nth Node From End of List 20.Valid Parentheses 21.Merge Two Sorted L
longest common prefix , 简单 valid number, hard, 用有限自动机 integer to roman ,easy , 模拟 roman to integer ,easy , 模拟 count and say , easy , 模拟 Anagrams 字符串处理,map Simplify Path,字符串处理,...
...The number of questions is increasing recently. Here is the classification of all `468` questions. ...I'll keep updating for full summary and better solutions....|-----|---------------- | --------------- |...
leetcode卡 LeetCode LeetCode题解 目录 字符串问题 ID Title C++ 难度 ...Common Prefix :star: 0038 Count and Say :star: 0043 Multiply Strings :star: :star: 大数相乘 0044 Wild Card Matchi
Longest Common Prefix 运行时间:40 毫秒内存使用:13.9 MB 20. Valid Parentheses 运行时间:40 毫秒内存使用:13.8 MB 22. Generate Parentheses 运行时间:164 毫秒内存使用:22.5 MB 26. Remove Duplicates ...
leetcode 答案programming-language-learning Javacript 复习基本DOM操作 C ...Longest Common Prefix 记得要判断strsSize = 0 && 1 的情况即可刚刚一直没判断会出现segment fault Python PHP Java
Flamg The flames of youth are raging. 解题口诀 动规递归是神器, 全无用处想哈希。 先用暴力得初解, 再据题意破玄奇。 贪心大法出身好, 正确路线永不倒。... Longest Common Prefix][27]][28] [!