Longet Common Prefix

2018.06.17

Algorithm

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.

나의 풀이

더 좋은 방법이 생각나지 않아서 일단 난폭하게 for 문 두 번 돌려서 풀어보기로 했다. 이렇게 하지 않고 푸는 방법이 있을까… 생각이 안 난다.
배열에 아무것도 들어있지 않은 경우도 고려한 문제였던 모양이다. 계속 런타임 에러가 나길래 보니 빈 배열이 들어가고 있었다.
for문을 두 번 돌렸지만, 어차피 prefix 찾는 거라서 앞에서 일치하는 경우 외에는 버리기 때문에 return으로 종료시켜 버렸다.

// 64ms
var longestCommonPrefix = function(strs) {
  const first = strs[0];
  if (first == null) return '';
  let str = '';
  for(let i = 0, il = first.length; i < il; i++) {
    for(let j = 1, jl = strs.length; j < jl; j++) {
      if(first[i] !== strs[j][i]) {
        return str;
      }
    }
    str += first[i];
  }
  return str;
};

// 60ms
var longestCommonPrefix = function(strs) {
  const first = strs[0];
  if (first == null) return '';
  const newStrs = strs.slice(1);
  let str = '';
  let i = 0;
  while(i < first.length) {
    if(newStrs.every((item) => item[i] === first[i])) {
      str += first[i]
    } else {
      return str;
    }
    i++;
  }
  return str;
}

배열의 every 메서드와 while로 풀어봤다. 속도가 크게 개선되지는 않았다.

다른 사람 풀이

// 50ms
var longestCommonPrefix = function(strs) {
  
  if(!strs.length) return '';
  if(strs.length === 1) return strs[0];
  
  let prefix = strs[0];
  
  for(let i in strs) {
    while(strs[i].indexOf(prefix) !== 0) {
      prefix = prefix.substring(0, prefix.length - 1);
      if(!prefix.length) return '';
    }
  }
   return prefix; 
};

나와 다른 접근법이다. 나는 배열에 있는 요소의 인덱스를 앞에서부터 돌면서 그 인덱스의 문자열이 모두 같으면 str에 더해서 prefix를 만들어 반환했는데,
여기는 일단 첫번째 문자열을 prefix라 가정하고 시작한다. 배열의 요소를 하나씩 순회하면서 prefix와 일치하는 문자열을 가지지 않으면 prefix에서 거꾸로 문자를 줄여가며 대조한다.

그렇다면 첫번째 문자열은 이미 prefix인데 for in문으로 첫번째 요소를 굳이 돌 필요가 있나 했는데, for loop로 인덱스 1부터 도는 것보다 어차피 while문 조건에 걸려서 다음 요소로 넘어가니까 for in문을 쓰는 게 더 빠른가보다.(환경에 따라 다를 수 있겠지만)

핵심은 indexOf의 사용인 것 같다. 문자열 하나씩 더하는 것보단 문자열 뭉치가 있는 지 확인하는 것이 더 효율적이니까.

// 56ms
var longestCommonPrefix = function(strs) {
  if(!strs.length) return '';
  if(strs.length === 1) return strs[0];
  let prefix = strs[0];
  for (let i = 1, l = strs.length; i < l; i++) {
    while(strs[i].indexOf(prefix) !== 0) {
      prefix = prefix.substring(0, prefix.length - 1);
      if(!prefix.length) return '';
    }
  }
  return prefix;
};