ภาพรวม
บทความนี้สาธิตวิธีตรวจสอบว่าอาร์เรย์สตริงที่จัดเรียงตามความยาว มีคุณสมบัติ Progressive: สตริงถัดไปเกิดจากการเพิ่มตัวอักษร 1 ตัวที่ด้านหน้าหรือด้านหลังของสตริงก่อนหน้า
ตัวอย่าง
['c', 'ca', 'can', 'acan', 'acane', 'dacane'] -> true
// c -> ca (+a ท้าย) -> can (+n ท้าย) -> acan (+a หน้า) -> acane (+e ท้าย) -> dacane (+d หน้า)
การนำไปใช้
const isProgressive = (arr) => {
for (let i = 0; i < arr.length - 1; i++) {
const next = arr[i + 1];
const current = arr[i];
// ตรวจสอบว่า next = char + current หรือ current + char
const nextLen = next.length;
if (next === next[0] + current || next === current + next[nextLen - 1]) {
continue;
}
return false;
}
return true;
};
console.log(isProgressive(['c', 'ca', 'can', 'acan', 'acane', 'dacane'])); // true
ผลลัพธ์
true
การปรับปรุง: Validation และ Edge Cases
const isProgressiveRobust = (arr) => {
if (!Array.isArray(arr) || arr.length < 2) return true;
// ตรวจสอบว่าเรียงตามความยาว
for (let i = 1; i < arr.length; i++) {
if (arr[i].length !== arr[i-1].length + 1) return false;
}
return arr.every((current, i) => {
if (i === 0) return true;
const next = arr[i];
return next.startsWith(current) || next.endsWith(current);
});
};
Dynamic Programming Connection
โจทย์นี้เกี่ยวข้องกับ String Chain หรือ Word Ladder Problem:
- Longest String Chain (LeetCode 1048)
- Word Ladder (LeetCode 127)
- DP State: dp[str] = max chain length ending at str
การประยุกต์ใช้
- Dictionary Validation: Word Building Games
- DNA Sequencing: Evolutionary Paths
- Code Generation: Incremental Code Construction
- Version Control: Incremental Diffs
