alt=”利用字典構建層級樹” />
1、問題背景
給定一個鍵值對字典，鍵是網頁名稱，值是網頁內容。網頁內容由其他網頁名稱組成，這些網頁名稱用空格分隔。目標是對于給定的網頁名稱，找到從首頁到該網頁的所有路徑。
例如，給定以下字典：
{ 'section-a.html': {'contents': 'section-b.html section-c.html section-d.html'}, 'section-b.html': {'contents': 'section-d.html section-e.html'}, 'section-c.html': {'contents': 'product-a.html product-b.html product-c.html product-d.html'}, 'section-d.html': {'contents': 'product-a.html product-c.html'}, 'section-e.html': {'contents': 'product-b.html product-d.html'}, 'product-a.html': {'contents': ''}, 'product-b.html': {'contents': ''}, 'product-c.html': {'contents': ''}, 'product-d.html': {'contents': ''} }
對于給定的網頁名稱 ‘product-d.html‘，應找到以下路徑：
‘section-a.html > section-b.html > section-e.html > product-d.html”section-a.html > section-c.html > product-d.html”section-a.html > section-d.html > product-c.html > product-d.html’
2、解決方案
為了解決這個問題，可以采用以下步驟：
- 將字典轉換成一個更易于使用的形式，即把網頁名稱作為鍵，網頁內容作為值。
- 根據網頁內容構建一個父網頁字典，其中鍵是網頁名稱，值是該網頁的父網頁列表。
- 對于給定的網頁名稱，從父網頁字典中找到其父網頁，并重復此步驟，直到找到首頁。
- 將從首頁到給定網頁的所有路徑存儲在一個列表中。
以下代碼實現了上述步驟：
function findPathsToItem(item, pages) { /** * Finds all paths from the home page to a given item. * @param {string} item - The item to find paths to. * @param {Object} pages - A dictionary of page names to page contents. * @returns {Array} A list of paths from the home page to the given item. */ // Convert the dictionary to a more usable form. let pageContents = {}; for (let [page, contents] of Object.entries(pages)) { pageContents[page] = new Set(contents.contents.split(' ')); } <p>// Build a parent page dictionary. let parentPages = {}; for (let page in pageContents) { parentPages[page] = []; for (let parentPage in pageContents) { if (pageContents[parentPage].has(page)) { parentPages[page].push(parentPage); } } }</p><p>// Find all paths from the home page to the given item. let paths = []; let partialPaths = [[item]]; while (partialPaths.length > 0) { let path = partialPaths.pop(); if (parentPages[path[path.length - 1]].length > 0) { // Add as many partial paths as open from here. for (let parentPage of parentPages[path[path.length - 1]]) { partialPaths.push([...path, parentPage]); } } else { // We've reached the home page. paths.push(path.reverse()); } } return paths; }</p><p>// Example usage let pages = { 'section-a.html': {'contents': 'section-b.html section-c.html section-d.html'}, 'section-b.html': {'contents': 'section-d.html section-e.html'}, 'section-c.html': {'contents': 'product-a.html product-b.html product-c.html product-d.html'}, 'section-d.html': {'contents': 'product-a.html product-c.html'}, 'section-e.html': {'contents': 'product-b.html product-d.html'}, 'product-a.html': {'contents': ''}, 'product-b.html': {'contents': ''}, 'product-c.html': {'contents': ''}, 'product-d.html': {'contents': ''} };</p><p>let paths = findPathsToItem('product-d.html', pages); console.log(paths);
輸出結果：
[ ['section-a.html', 'section-b.html', 'section-e.html', 'product-d.html'], ['section-a.html', 'section-c.html', 'product-d.html'], ['section-a.html', 'section-d.html', 'product-c.html', 'product-d.html'] ]
