Longest Common Prefix

문자열 배열을 받으면 배열안에 요소를 검사하여 공통적인 접두사를 찾는 문제이다.

Input: strs = ["flower","flow","flight"]
Output: "fl"
Input: strs = ["dog","racecar","car"]
Output: ""

처음 문제를 보았을때 이중 for문을 이용하여 접근하면 좋을거 같아서 작업하였지만 문제를 해결못하고 결국 구글링의 힘을 빌렸다.
아래의 방법은 set 를 이용하여 이중 for문으로 뽑아낸 요소 중복을 제거하여 검사하는 알고리즘이다.

set은 유일값을 보장하기 때문에 가능한 방법이다.

var longestCommonPrefix = function (strs) {
  let result = '';
  outer: for (let i = 0; i < strs[0].length; i++) {
    let set = new Set();
    let item = '';

    for (let j = 0; j < strs.length; j++) {
      item = strs[j][i];
      set.add(item);
    }

    if (set.size === 1) {
      result += item;
    } else {
      break outer;
    }
  }
  console.log(result);
  return result;
};

성능이 너무 안좋아보여 다른방법을 찾아보았다 strs 를 먼저 sort하여 첫번째 요소와 마지막 요소만을 검사하는 알고리즘이다 내가 알고있는 함수들인데 이렇게 쓰인다는게 놀라웠고 왜 이런생각을 못했을까 생각도 들었다.

var longestCommonPrefix = function(strs) {
    strs.sort();
    for(let i =0; i <= strs[0].length; i++){
        if(strs[strs.length -1][i] !== strs[0][i]){
            return strs[0].substring(0,i)
        }
    }
    return strs[0];
};