143 lines
7.8 KiB
HTML
143 lines
7.8 KiB
HTML
<!DOCTYPE html>
|
||
<html lang="zh-Hans">
|
||
<head>
|
||
<meta charset="UTF-8">
|
||
<meta name="viewport" content="width=device-width, initial-scale=1.0">
|
||
<title>095. 编辑距离 – 图解</title>
|
||
<link rel="stylesheet" href="../shared/style.css">
|
||
<style>
|
||
/* page-specific overrides */
|
||
.vis-area { min-height: 120px; padding: 16px 0; }
|
||
.code-section { margin-top: 16px; }
|
||
</style>
|
||
</head>
|
||
<body>
|
||
<div class="container">
|
||
<h1>🟡 095. 编辑距离 <span class="badge medium">中等</span></h1>
|
||
<p class="subtitle">分类：多维动态规划 ｜ LeetCode Hot 100</p>
|
||
|
||
<!-- 控制面板 -->
|
||
<div class="controls" id="controls">
|
||
<label for="inputArea">输入：</label>
|
||
<input type="text" id="inputArea" placeholder="默认示例，可自定义">
|
||
<button id="applyBtn" class="primary">生成图解</button>
|
||
<select id="exampleSelect"></select>
|
||
<span style="flex:1"></span>
|
||
<button id="prevBtn">◀ 上一步</button>
|
||
<button id="nextBtn">下一步 ▶</button>
|
||
<button id="jumpBtn">⏭ 跳到结果</button>
|
||
<button id="autoBtn">自动播放</button>
|
||
<button id="resetBtn">重置</button>
|
||
</div>
|
||
|
||
<!-- 步骤流水线 -->
|
||
<div class="pipeline" id="pipeline"></div>
|
||
|
||
<!-- 提示条 -->
|
||
<div class="hint info" id="hintBox">
|
||
<span id="stepInfo"></span><br>
|
||
<span id="hintText"></span>
|
||
</div>
|
||
|
||
<!-- 可视化面板 -->
|
||
<div class="panels">
|
||
<div class="panel" id="mainPanel">
|
||
<h3>📊 可视化</h3>
|
||
<div class="vis-area" id="vizArea">点击「生成图解」开始</div>
|
||
</div>
|
||
<div class="panel-grid">
|
||
<div class="panel" id="detailPanel">
|
||
<h3>📝 当前步骤详情</h3>
|
||
<div id="detailContent">等待开始...</div>
|
||
</div>
|
||
<div class="panel" id="resultPanel">
|
||
<h3>✅ 结果</h3>
|
||
<div id="resultContent">等待完成...</div>
|
||
</div>
|
||
</div>
|
||
</div>
|
||
|
||
<!-- 代码 -->
|
||
<div class="panel code-section">
|
||
<h3>💻 参考代码（Python）</h3>
|
||
<div id="codeArea"></div>
|
||
</div>
|
||
|
||
<footer>Powered by QwenPaw · 图解算法 · LeetCode Hot 100</footer>
|
||
</div>
|
||
|
||
<script src="../shared/algo-viz.js"></script>
|
||
<script>
|
||
"use strict";
|
||
(function() {
|
||
// ========== Algorithm Logic ==========
|
||
|
||
const examples = [
|
||
{s1:'horse', s2:'ros', label:'示例1: "horse"→"ros"'},
|
||
{s1:'intention', s2:'execution', label:'示例2: "intention"→"execution"'},
|
||
{s1:'kitten', s2:'sitting', label:'示例3: "kitten"→"sitting"'},
|
||
];
|
||
let steps, stepCtrl, str1, str2, m, n;
|
||
function buildSteps(a, b) {
|
||
str1=a;str2=b;m=a.length;n=b.length;steps=[];
|
||
const dp=[];for(let i=0;i<=m;i++) dp[i]=new Array(n+1).fill(0);
|
||
steps.push({stage:'init',msg:`构建 (${m}+1)×(${n}+1) DP 表`,dp:dp.map(r=>[...r]),row:-1,col:-1});
|
||
for(let i=0;i<=m;i++)dp[i][0]=i;for(let j=0;j<=n;j++)dp[0][j]=j;
|
||
steps.push({stage:'base',msg:'边界: dp[i][0]=i(删除), dp[0][j]=j(插入)',dp:dp.map(r=>[...r]),row:-1,col:-1});
|
||
for(let i=1;i<=m;i++) for(let j=1;j<=n;j++){
|
||
if(a[i-1]===b[j-1]){dp[i][j]=dp[i-1][j-1];steps.push({stage:'match',msg:`w1[${i-1}]='${a[i-1]}'==w2[${j-1}]='${b[j-1]}'→dp=${dp[i][j]}`,dp:dp.map(r=>[...r]),row:i,col:j,op:'match'});}
|
||
else{const ins=dp[i][j-1]+1,del=dp[i-1][j]+1,rep=dp[i-1][j-1]+1;dp[i][j]=Math.min(ins,del,rep);
|
||
let opN=rep<=Math.min(ins,del)?'替换':(ins<=del?'插入':'删除');
|
||
steps.push({stage:'op',msg:`'${a[i-1]}'≠'${b[j-1]}'→插=${ins}删=${del}替=${rep}→${dp[i][j]}(${opN})`,dp:dp.map(r=>[...r]),row:i,col:j,op:opN});}
|
||
}
|
||
const ops=[];let ti=m,tj=n;while(ti>0||tj>0){if(ti>0&&tj>0&&a[ti-1]===b[tj-1]){ti--;tj--;}else if(ti>0&&tj>0&&dp[ti][tj]===dp[ti-1][tj-1]+1){ops.unshift(`替换 '${a[ti-1]}'→'${b[tj-1]}'`);ti--;tj--;}else if(tj>0&&dp[ti][tj]===dp[ti][tj-1]+1){ops.unshift(`插入 '${b[tj-1]}'`);tj--;}else{ops.unshift(`删除 '${a[ti-1]}'`);ti--;}}
|
||
steps.push({stage:'done',msg:`编辑距离=${dp[m][n]}`,dp:dp.map(r=>[...r]),row:m,col:n,ops:[...ops]});
|
||
}
|
||
function render(step) {
|
||
const s=steps[step];
|
||
let viz='<div style="overflow-x:auto;"><table style="border-collapse:collapse;font-size:14px;">';
|
||
viz+='<tr><td style="border:1px solid #e2e8f0;padding:6px 10px;background:#f1f5f9;"></td><td style="border:1px solid #e2e8f0;padding:6px 10px;background:#f1f5f9;">∅</td>';
|
||
for(let j=0;j<n;j++) viz+=`<td style="border:1px solid #e2e8f0;padding:6px 10px;background:#f1f5f9;">${str2[j]}</td>`;
|
||
viz+='</tr>';
|
||
for(let i=0;i<=m;i++){viz+='<tr>';viz+=`<td style="border:1px solid #e2e8f0;padding:6px 10px;background:#f1f5f9;">${i===0?'∅':str1[i-1]}</td>`;
|
||
for(let j=0;j<=n;j++){let bg='white',fw='normal';if(s.row===i&&s.col===j){bg='#fef3c7';fw='bold';}else if(s.dp[i][j]>0&&!(i===0&&j===0)){bg='#ecfdf5';}else if(i===0||j===0){bg='#f1f5f9';}
|
||
const ic=s.row===i&&s.col===j&&s.op==='match'?' ✅':s.row===i&&s.col===j&&s.op==='替换'?' 🔄':s.row===i&&s.col===j&&s.op==='插入'?' ➕':s.row===i&&s.col===j&&s.op==='删除'?' ➖':'';
|
||
viz+=`<td style="border:1px solid #e2e8f0;padding:6px 10px;text-align:center;background:${bg};font-weight:${fw};min-width:40px;">${s.dp[i][j]}${ic}</td>`;}
|
||
viz+='</tr>';}
|
||
viz+='</table></div><div style="margin-top:10px;display:flex;gap:12px;font-size:12px;color:#64748b;"><span>✅相同</span><span>🔄替换</span><span>➕插入</span><span>➖删除</span></div>';
|
||
$('vizArea').innerHTML=viz;
|
||
let detail='<div class="calc-block">'+s.msg+'</div>';if(s.ops){detail+='<div style="margin-top:8px;"><b>操作：</b></div>';s.ops.forEach((o,i)=>{detail+=`<div>${i+1}. ${o}</div>`;});}$('detailContent').innerHTML=detail;
|
||
if(s.stage==='done') $('resultContent').innerHTML=`<div class="final-answer">编辑距离=<b>${s.dp[m][n]}</b><br>${s.ops.join(' → ')}</div>`;
|
||
$('hintText').textContent=s.msg;
|
||
const stages=['init→初始化','base→边界','match→匹配','op→操作','done→完成'];
|
||
$('pipeline').innerHTML=stages.map(x=>{const[k,l]=x.split('→');return`<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;}).join('<i>→</i>');
|
||
}
|
||
function init() {
|
||
const sel=$('exampleSelect');examples.forEach((e,i)=>{sel.innerHTML+=`<option value="${i}">${e.label}</option>`;});
|
||
$('inputArea').value='word1="horse", word2="ros"';buildSteps(examples[0].s1,examples[0].s2);
|
||
stepCtrl=new StepController({onStep:render});stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent='步骤 1 / '+steps.length;stepCtrl.onStep=(idx)=>{render(idx);$('stepInfo').textContent=`步骤 ${idx+1} / ${steps.length}`;};
|
||
$('applyBtn').onclick=()=>{const v=$('inputArea').value.match(/word1\s*=\s*"([^"]+)".*word2\s*=\s*"([^"]+)"/);if(!v){alert('格式: word1="horse", word2="ros"');return;}buildSteps(v[1],v[2]);stepCtrl.setSteps(steps.map((_,i)=>i));render(0);};
|
||
$('exampleSelect').onchange=()=>{const e=examples[parseInt($('exampleSelect').value)];$('inputArea').value=`word1="${e.s1}", word2="${e.s2}"`;buildSteps(e.s1,e.s2);stepCtrl.setSteps(steps.map((_,i)=>i));render(0);};
|
||
$('prevBtn').onclick=()=>stepCtrl.prev();$('nextBtn').onclick=()=>stepCtrl.next();$('jumpBtn').onclick=()=>stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick=()=>{const on=stepCtrl.toggleAuto();$('autoBtn').textContent=on?'暂停':'自动播放';};
|
||
$('resetBtn').onclick=()=>{stepCtrl.reset();$('autoBtn').textContent='自动播放';};
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def minDistance(word1, word2):
|
||
m, n = len(word1), len(word2)
|
||
dp = [[0]*(n+1) for _ in range(m+1)]
|
||
for i in range(m+1): dp[i][0] = i
|
||
for j in range(n+1): dp[0][j] = j
|
||
for i in range(1, m+1):
|
||
for j in range(1, n+1):
|
||
if word1[i-1] == word2[j-1]:
|
||
dp[i][j] = dp[i-1][j-1]
|
||
else:
|
||
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
|
||
return dp[m][n]`, {lang:'Python'});
|
||
|
||
})();
|
||
</script>
|
||
</body>
|
||
</html> |