공통된 가장 긴 문자열을 찾아라

정은경·2019년 12월 16일
0

*문제
strs은 단어가 담긴 배열입니다.
공통된 시작 단어(prefix)를 반환해주세요.

예를 들어
strs = ['start', 'stair', 'step']
return은 'st'

strs = ['start', 'wework', 'today']
return은 ''


const getPrefix = strs => {
  if(strs.length == 0){
    return ''
  }
  
  min = strs[0].length;
  list_num = strs.length;
  rlt ="";
  
  for (i of strs){
    if(min>i.length){
      min = i.length;
    }
  }

  
  for(let i=0; i<min; i++){
    temp = strs[0][i]
    count = 0
    for(let j=0; j<list_num; j++){
      if(strs[j][i]==temp){
        count += 1
      }else{
        break;
      }
    }
    if(count==list_num){
      rlt+=temp
    }
  }
  return rlt
  
  
}


getPrefix([])
profile
#의식의흐름 #순간순간 #생각의스냅샷

1개의 댓글

comment-user-thumbnail
2019년 12월 17일

이럴경우 시간복잡도가 O(LN) (L은 문자열의 길이 N 은 총 문자열 갯수) 가 되는데
Trie 을 사용하면 O(Max(L,N)) 이 되지 않을까요?

답글 달기