LeetCode #14. Longest Common Prefix プログラミング練習
問題:
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Example 1:
Input: ["flower","flow","flight"]
Output: "fl"
Example 2:Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:All given inputs are in lowercase letters a-z.
難易度: easy
入力: String型Array
目的: 入力Stringの中で最長の共通頭文字を示せ
出力: String
共通の頭文字を探す為に、どうしても共通部分を一つずつチェックしていく必要があります。
ただこう言った問題はテストケースに共通部分がとても長いケースがあるので、
共通部分を一文字ずつ追加していくよりも一文字ずつ減らして行く考え方の方が速くなります。
注意すべき事:
- 共通部分がない場合は空文字列を返す。
以下回答です。
class Solution { public String longestCommonPrefix(String[] strs) { int len = strs.length; int minIndex = 0; int minLen = Integer.MAX_VALUE; String minSub = ""; if( len == 1) { return strs[0]; } if (len == 0) { return ""; } for(int i=0; i<len; i++) { int temp = strs[i].length(); if (minLen > temp) { minLen = temp; minIndex = i; } } for(int i=minLen; i>=0; i--) { minSub = strs[minIndex].substring(0,i); int j = 0; for(; j<len; j++){ String temp = strs[j].substring(0,i); if(!minSub.equals(temp)) { break; } } if(j == len) { return minSub; } } return minSub; } }
まず入力された行列の中で一番短い単語をベースにしてチェックしていく。
入力された文字列群とチェックしていき、
一文字でも違う場合はbreak、ベースの最後の一文字を破棄しこれを繰り返す。
breakせずにfor loopを完走した場合そのまま出力
今日は以上。
ではでは