가장 긴 공통 부분 문자열

WooBuntu·2020년 8월 30일
0

JS 100제

목록 보기
12/34

가장 긴 공통 부분 문자열

function longestCommonSubsequence(former, latter) {
  const longer = former.length > latter.length ? former : latter;
  const shorter = longer == former ? latter : former;
  let returnStr = "";
  for (let lengthOfPiece = shorter.length; lengthOfPiece > 1; lengthOfPiece--) {
    let concat = "";
    let copyOfLonger = longer.slice();

    for (let i = 0; i < shorter.length - lengthOfPiece + 1; i++) {
      const sliced = shorter.slice(i, i + lengthOfPiece);
      const indexOfMatched = copyOfLonger.indexOf(sliced);
      if (indexOfMatched != -1) {
        copyOfLonger = copyOfLonger.split("");
        copyOfLonger.splice(0, indexOfMatched + lengthOfPiece);
        copyOfLonger = copyOfLonger.join("");
        concat += sliced;
        debugger;
      }
    }
    if (concat.length > returnStr.length) {
      returnStr = concat;
    }
    debugger;
  }
  return returnStr;
}
  • 테스트케이스 3번의 출력이 6이어야 할 때의 풀이이다.
function longestCommonSubsequence(former, latter) {
  const longer = former.length > latter.length ? former : latter;
  const shorter = longer == former ? latter : former;
  for (let lengthOfPiece = shorter.length; lengthOfPiece > 1; lengthOfPiece--) {
    for (let i = 0; i < shorter.length - lengthOfPiece + 1; i++) {
      const sliced = shorter.slice(i, i + lengthOfPiece);
      const indexOfMatched = longer.indexOf(sliced);
      if (indexOfMatched != -1) {
        return sliced;
      }
    }
  }
}
  • 테스트케이스 3번의 출력이 3이어야 할 때의 풀이이다.

0개의 댓글