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'] ]
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
