JavaScript를 사용하여 이진 문자열에서 최소 뒤집기 찾기

<시간/>

단조 증가하는 문자열:

'0'과 '1'의 문자열은 '0'(0일 수도 있음) 뒤에 오는 '1'(0일 수도 있음)로 구성된 경우 단조 증가합니다.

문제

이진 문자열 str을 첫 번째이자 유일한 인수로 취하는 JavaScript 함수를 작성해야 합니다.

문자열에 있는 '0'을 '1'로 또는 '1'을 '0'으로 뒤집을 수 있습니다. 우리 함수는 S가 단조롭게 증가하도록 최소 뒤집기 횟수를 반환해야 합니다.

예를 들어, 함수에 대한 입력이

인 경우

입력

const str = '00110';

출력

const output = 1;

출력 설명

마지막 '0'을 '1'로 바꾸면 문자열 '00111'이 남게 되기 때문입니다.

예시

const str = '00110';
const countFlips = (str = '') => {
   const map = {}
   const helper = (index, prev) => {
      map[index] = map[index] || {}
      if (map[index][prev] !== undefined) {
         return map[index][prev]
      }
      if (index >= str.length) {
         return 0
      }
      if (prev === '0') {
         if (str[index] === '0') {
            map[index][prev] = Math.min(helper(index + 1, '0'), helper(index + 1, '1') + 1)
      } else {
         map[index][prev] = Math.min(helper(index + 1, '1'), helper(index + 1, '0') + 1)
      }
      } else if (str[index] === '0') {
         map[index][prev] = helper(index + 1, '1') + 1
      } else {
         map[index][prev] = helper(index + 1, '1')
      }
         return map[index][prev]
      }
   return helper(0, '0')
};
console.log(countFlips(str));