การหาสตริงย่อยสั้นที่สุดที่ครอบคลุมตัวอักษรทั้งหมดใน JavaScript

บทความนี้สาธิตอัลกอริทึม "Minimum Window Substring" หาสตริงย่อยสั้นที่สุดใน str1 ที่มีตัวอักษรครบทุกตัวที่อยู่ใน str2

ตัวอย่าง

const str1 = 'abcdefgh';
const str2 = 'gedcf';
// ผลลัพธ์: 'cdefg'

ตัวอย่างโค้ด

const str1 = 'abcdefgh';
const str2 = 'gedcf';

const subIncludesAll = (str, str2) => {
  for (let i = 0; i < str.length; i++) {
    if (str2.indexOf(str[i]) !== -1) {
      str2 = str2.replace(str[i], '');
    }
  }
  return (str2.length === 0);
};

const minWindow = (str1 = '', str2 = '') => {
  let shortestString = null;
  for (let i = 0; i < str1.length; i++) {
    for (let j = i; j < str1.length; j++) {
      let testString = str1.substr(i, j - i + 1);
      if (subIncludesAll(testString, str2)) {
        if (shortestString === null || testString.length < shortestString.length) {
          shortestString = testString;
        }
      }
    }
  }
  return shortestString;
};

console.log(minWindow(str1, str2));

ผลลัพธ์

cdefg

คำอธิบาย

ใช้ brute force ตรวจสอบทุก substring ที่เป็นไปได้ของ str1 (O(n^2)) และใช้ helper function ตรวจสอบว่ามีตัวอักษรครบ str2 หรือไม่

หมายเหตุ: วิธีนี้มีประสิทธิภาพต่ำสำหรับสตริงยาว ควรใช้ sliding window algorithm เพื่อ O(n)