LeetCode - longest common prefix

katanazero86·2020년 5월 26일
0

leetcode

목록 보기
3/13
post-thumbnail

longest common prefix

  • Difficulty : easy

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
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.

Example 3:
Input: ["aca","cba"]
Output: ""
Explanation: There is no common prefix among the input strings.

solution

  • 작성 언어 : javascript
// 초기 코드
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    
};
  • leet code runtime 72 ms
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    
    if(strs.length === 0) {
        return '';
    }   

    const commonPrefix = strs.reduce((commonPrefix, currentString, currentIndex) => {        
        let returnCommonPrefix = '';
                       
        for(let i=0; i < commonPrefix.length; i++) {
            if(commonPrefix[i] === currentString[i]) {
                returnCommonPrefix += commonPrefix[i];
            } else {
                break;
            }
            
            if(!currentString[i]) {
                break;
            }
        }
        
        return returnCommonPrefix;
        
    });
        
    return commonPrefix;
    
};
  • reduce() 메서드를 이용하여 작성
  • 처음 실행하면 commonPrefix 의 값은 strs[0] 값이 들어있으며, currentString 과 문자를 하나씩 비교를 한다.
  • 만약 첫글자부터 틀리면 더 이상 for 문을 반복할 이유가 없기때문에 break 해준다.
  • 같은게 있다면, 그걸 반환해주고 그 공통 접두사를 기준으로 다음 문자를 하나씩 비교해준다.
  • 공통 접두사이기 때문에 한 단어라도 처음에 일치하지 않으면 걸러야한다.
  • 실행시간이 빠른코드 답안을 보니, .some() 를 사용한게 눈에 뛴다.

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    
    if(strs.length === 0) {
        return '';
    }
    
    // 가장 길이가 작은 문자열이 앞에 오도록 정렬(오름차순)
    strs.sort((a,b) => {
       if(a.length > b.length) {
           return 1
       }
        
       if(b.length > a.length) {
           return -1
       }
        
       return 0;
    });

    
    let commonPrefix = '';
    let maxLength = strs[0].length;
    
    for(let i = 0; i < maxLength; i++) {
      const char = strs[0][i];
       if (strs.some(str => str[i] !== char)) {
          return commonPrefix;
        } else {
          commonPrefix += char;
        }
    }
    
    return commonPrefix;  
    
};
  • 이런식으로 고쳐봤는데, 수행시간이 비스무리하다;; 뭐지..
  • Array.some() 는 배열요소 중에 하나라도 특정조건을 만족하는지 사용하면 좋다.
profile
developer life started : 2016.06.07 ~ 흔한 Front-end 개발자(현재는 백수 얏호👻)

0개의 댓글