LeetCode - longest common prefix

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() 는 배열요소 중에 하나라도 특정조건을 만족하는지 사용하면 좋다.