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

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

자주 다루는 코딩테스트 문제를 가져왔습니다.

#146. WordBreak2

문제 설명) 비어있지 않은 string s와 비어 있지 않은 단어 list를 포함하는 wordDict가 존재한다.

String s에 빈 공간을 줘서 문장을 형성하고 각 단어는 wordDict안에 들어있는 값들이다.

모든 가능한 문장들을 return해라.

조건)  같은 단어를 여러 번 재사용 가능하다. (Segmentation: 분할)

 

 

코드풀이) JavaScript

/**


 * @param {string} s


 * @param {string[]} wordDict


 * @return {string[]}


 */


var wordBreak = function (s, wordDict, cache = new Map()) {


  if (cache.has(s))


    return cache.get(s);


  if (s.length === 0) {


    cache.set(s, []);


    return [];


  }


  const result = [];


  for (let word of wordDict) {


    const index = s.indexOf(word);


    if (index === 0) {


      const newStr = s.slice(word.length);


      const values = wordBreak(newStr, wordDict, cache);


      if (values.length === 0 && newStr.length === 0)


        result.push(word);


      else {


        values.forEach(val => {


          result.push(word + ' ' + val);


        });


      }


    }


  }


  cache.set(s, result);


  return result;


}

[문제풀때 필요한 JavaScript 표준 내장 객체인 String prototype method]

var s = 'testcodeboogie'


console.log(s.slice(4))


console.log(s.indexOf('stc'))


console.log(s.indexOf('stc2'))


console.log(s.substring(0, 4))

 

결과(output)

codeboogie

2

-1

test

알고리즘)

전형적인 Dynamic Programming의 문제로

indexOf의 값이 0이 는 값을 찾을때까지 for문을 돌린다.

제일 처음에 시작하는 해당문자열에서 부터 시작하여 찾으면

Slice를 통해 해당 단어를 문자열에서 지우고 그 이후부터 다시 함수를 출력한다.