[leetCode] Longest Common Prefix

14 . 가장 긴 공통 접두사

 

문자열 배열 중에서 가장 긴 공통 접두사 문자열을 찾는 함수를 작성하십시오.

공통 접두사가 없으면 빈 문자열을 반환합니다 "".

 

예 1:

입력: strs = ["flower","flow","flight"]
 출력: "fl"

예 2:

입력: strs = ["dog","racecar","car"]
 출력: ""
 설명: 입력 문자열 사이에 공통 접두사가 없습니다.

 

제약:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i]영문 소문자로만 구성되어 있습니다.

문제정리
1. strs 배열이 주어지면 그안에 문자열중에 공통된 문자열을 찾는 문제이다.

문제조건
1. 공통 문자열이 없으면 빈 문자열을 반환한다.

생각한 풀이방법
1. 첫번째 문자열의 i번째 길이와, 두번째 문자열의 i번째 길이를 비교해서  문자열이 같으면 넘어가고 다른 문자열이 나올때까지 반복문을 돌린다.
2. 비교된 문자열의 길이가 서로 다른 문자열이 나오면, 다른 문자열이 나온 부분까지 잘라내고 잘라낸 문자열은 변수에 넣어준다.
3. 가장긴 문자열이 저장된 변수와 0을 비교했을때 같다면 빈 문자열을 리턴해준다.

 

작성코드🎈

function longestCommonPrefix(strs) {
let prefix = strs[0];

for (let i = 1; i < strs.length; i++) {
  for (let j = 0; j < prefix.length; j++) {
    if (strs[i][j] !== prefix[j]) {
      prefix = prefix.substring(0, j);
      break;
    }
  }

  if (prefix.length === 0) {
    return "";
  }
}

return prefix;
};

 

1. 첫번째 for문은 strs의 두번째 문자열부터 마지막 문자열까지 반복해기위한 for문

첫번째 for문에서 i = 1; 로 선언한 이유는?

초기값으로 첫번째 문자열을 잣대로 세워놓고 그 잣대와 strs 배열의 두 번째 문자열부터 순회해야하기 때문

 

2. 두번째 for문에서는 prefix 문자열(strs[0]번째) 과 strs[i] 문자열의 같은 위치의 문자를 비교해준다.

예를들어 strs = ['flower', 'flow', 'fly'] 가 있다면 prefix에는 strs[0]번째인 flower를 넣어놓고, 

strs[i][j]인 flow의 j번째를 가져온다. prefix[j]에도 prefix에 넣어주었던flower의 j번째를 가져와 비교해준다. 

j변수를 만약 i + 1로 초기화하면, 어떻게 될까?

prefix 문자열의 일부 문자열이 제거되기 때문에, 이후에 prefix 문자열에서 순회해야 하는 위치가 변경된다.

j 변수는 항상 0부터 시작해야 한다.

 

3. 조건문을 사용하여 strs[i][j] 와 prefix[j] 가 다르면 prefix 문자열을 substring 메서드를 사용하여 비교점부터

현재 위치까지 문자열로 잘라내준다. (prefix의 현까지의 문자열을 가져옴)

 

4. strs[i][j] 와 prefix[j] 의 문자가 다르면, prefix 문자열을 substring 메서드를 사용하여 현재 위치까지 짤라낸다.

만약 문자열이 같으면 if 조건문이 실행되지 않고, 다음 인덱스로 넘어가서 다시 비교를 진행한다.

break를 하는 이유는? 

조건이 성립하면 바로 반복문을 종료시켜야하기때문에. => 반복문을 종료하고, 현재까지 비교했던 문자열에서 공통 prefix가 끝난 지점까지만 prefix 변수에 저장

 

5. prefix.legnth === 0일 경우엔, 즉 문자열이 없을땐, '' 빈값을 리턴한다.