การหาจำนวนการพลิกน้อยที่สุดในสตริงฐานสองด้วย JavaScript

สตริงเพิ่มขึ้นอย่างเด็ดขาด (Monotonically Increasing String)

สตริงของ '0' และ '1' ถือว่าเพิ่มขึ้นอย่างเด็ดขาด หากมันประกอบด้วย '0' จำนวนหนึ่ง (อาจเป็น 0) ตามด้วย '1' จำนวนหนึ่ง (อาจเป็น 0)

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับสตริงฐานสอง str เป็นอาร์กิวเมนต์เดียว

เราสามารถพลิก '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));

ผลลัพธ์

1