[자바JAVA]14. Longest Common Prefix

문제 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 “”.
strs[i] consists of only lower-case English letters.

• 입출력예시

//예시1
Input: strs = ["flower","flow","flight"]
Output: "fl"

//예시2
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

풀이 코드

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String prefix="";
        if(strs.length == 0) return prefix;
        prefix = strs[0];

        for(int i=1; i<strs.length; i++){
            String cur = strs[i];
            while(cur.indexOf(prefix) != 0){
                prefix = prefix.substring(0, prefix.length()-1);
            }
        }
        return prefix;
    }
}

배운 지식

indexOf()를 사용할 생각을 못했다.
indexOf()는 주어진 요소가 배열에 있다면 그 첫번째 인덱스 값를 반환하고 없으면 -1을 반환한다.

아래 3가지 모두 0을 리턴한다.

"ant".indexOf("ant") => 0
"ant".indexOf("an") => 0
"ant".indexOf("a") => 0

strs[0]전체를 prefix로 두고 만약 strs[1]과 일치하지 않는다면 strs[0]의 마지막 char를 지워나가는 방식이다.
예를 들어 strs배열이 아래와 같다고 하자.

strs[0] = "flower"
strs[1] = "flow"
strs[2] = "flight"

1. for문 시작 i=1일때,
   flow에 flower가 속해있지않다. -> prefix에서 flower의 마지막 char인 r을 제거 -> 다시 while문
   flow에 flowe가 속해있지않다. -> prefix에서 flowe의 마지막 char인 e를 제거 -> 다시 while문
   flow에 flow가 0번째로 속해있다. -> prefix는 flow가 되고 while문 종료

2. for문 시작 i=2일때,
   flight에 flow가 속해있지않다. -> prefix에서 flow의 마지막 char인 w을 제거 -> 다시 while문
   flight에 flo가 속해있지않다. -> prefix에서 flo의 마지막 char인 o를 제거 -> 다시 while문
   flight에 fl가 0번째로 속해있다. -> prefix는 fl가 되고 while문 종료

항상 생각의 전환을 하자. 항상 더 나은 코드가 있다.

다른 문제 풀이가 보고싶다면?

• 모든 릿코드(LeetCode)(leetcode) java 풀이