[ 코딩테스트 JS ] 자바스크립트 코테 05 ( JavaScript )

JavaScript 자바스크립트 코딩테스트 05

많은 스타트업에서 자주 다루는 코딩테스트 문제를 가져왔습니다.

먼저 첫 문제부터 시작하겠습니다. 전에 올렸던 코딩테스트 04에서 이어지는 

문제입니다.

#139. Word Break

문제)

s가 하나 이상의 사전 단어의 공백으로 구분 된 시퀀스로 분할 될 수 있는지 여부를 결정합니다.

코드풀이) JavaScript Using BFS
( 단어 하나씩 추가하면서 전체 경우의 수 대입하여 해당하는 조건문 찾기 )

/**


 * @param {string} s


 * @param {string[]} wordDict


 * @return {boolean}


 */


var wordBreak = function(s, wordDict) {


    if (wordDict.length === 0) return false;


    if (wordDict.length === 1) return s === wordDict[0];


    


    let queue = [''];


    let memo = new Map();


    


    while (queue.length > 0) {


        const val = queue.shift();


        


        for (let word of wordDict) {


            const searchWord = `${val}${word}`;


            const startsWith = s.indexOf(searchWord) === 0;


            


            if (searchWord === s) return true;


            else if (!memo.has(searchWord) && startsWith) {


                memo.set(searchWord, true);


                queue.push(searchWord);


            }


        }


    }



    return false;


};

자바Code (ex) 2가지 방식의 풀이가 있습니다.

public class Solution {


  public boolean wordBreak (String s, Set<String> dict) {


  boolean[] f = new boolean[s.length() + 1];


  f[0] = true;


  /* First DP


  for(int i=1; i<=s.length(); i++){


    for(String str: dict){


      if(f[i-str.length]){


        if(s.substring(i-str.length(), i).equals(str)){


          f[i] =true;


          break;


        }


      }


    }


  }


  */


  //Second DP


  for (int i = 1; i <= s.length(); i++) {


    for (int j = 0; j < i; j++) {


      if (f[j] && dict.contains(s.substring(j, i))) {


        f[i] = true;


        break;


      }


    }


  }


  return f[s.length()]


}


}

 

#5. Longest Palindromic Substring 

 

문제)

String이 주어졌을때, 가장 긴 palindrome을 찾아라. String의 maximum length는 1000이다.

예시)

Input : "babad"

Output: "bab"

Note: "aba" is also a valid answer.

코드 풀이)

/**

 * @param {string} s

 * @return {string}

 */

var longestPalindrome = function (s) {

  var max = '';

  for (var i = 0; i < s.length; i++){

    for(var j=0; j<2;j++){

      var left= i;

      var right = i+j;

      while(s[left] && s[left] === s[right]){

        left--;

        right++;

      }

      if((right -left -1)>max.length){

        max= s.substring(left+1, right);

      }

    }

  }

  return max;

};

사용된 표준 내장 객체 String의 원형 메소드

String.prototype.substring()

const str = 'Mozilla';

 

console.log(str.substring(1, 3));

// expected output: "oz"

 

console.log(str.substring(2));

// expected output: "zilla

 

var anyString = 'Mozilla';

// Displays 'M'
console.log(anyString.substring(0, 1));
console.log(anyString.substring(1, 0));

// Displays 'Mozill'
console.log(anyString.substring(0, 6));

// Displays 'lla'
console.log(anyString.substring(4));
console.log(anyString.substring(4, 7));
console.log(anyString.substring(7, 4));

// Displays 'Mozilla'
console.log(anyString.substring(0, 7));
console.log(anyString.substring(0, 10));