php - 使用 PHP 获取最深的文件路径

Question

有谁知道如何从具有文件路径的数组中获取具有最深路径的元素？如果这听起来很奇怪，想象一下以下数组：

/a/b
/a
/1/2/3/4
/1/2
/1/2/3/5
/a/b/c/d/e

我想要得到的是：

/1/2/3/4
/1/2/3/5
/a/b/c/d/e

想知道最快的方法是什么，而不必一遍又一遍地遍历整个数组。语言是 PHP (5.2)。

Answer 1

$aPathes = array(
    '/a/b',
    '/a',
    '/1/2/3/4',
    '/1/2',
    '/1/2/3/5',
    '/a/b/c/d/e'
);

function getDepth($sPath) {
    return substr_count($sPath, '/');
}
$aPathDepths = array_map('getDepth', $aPathes);
arsort($aPathDepths);
foreach ($aPathDepths as $iKey => $iDepth) {
    echo $aPathes[$iKey] . "\n";
}

另请参阅此示例。

=== 更新 ===

$aUsed = array();
foreach ($aPathes as $sPath) {
    foreach ($aUsed as $iIndex => $sUsed) {
        if (substr($sUsed, 0, strlen($sPath)) == $sPath || substr($sPath, 0, strlen($sUsed)) == $sUsed) {
            if (strlen($sUsed) < strlen($sPath)) {
                array_splice($aUsed, $iIndex, 1);
                $aUsed[] = $sPath;
            }
            continue 2;
        }
    }
    $aUsed[] = $sPath;
}

另请参阅此示例。

Answer 2

根据您的说明，这是一个可以做到的功能。它保留一个找到的“最深路径”数组，并将每条路径与其进行比较。最好情况是 O(n)（如果所有路径都是最大路径的子路径），最坏情况是 O(n ² )（如果所有路径完全不同）。

请注意，这continue 2意味着“继续外循环”。

<?php

function getDeepestPaths($array)
{
    $deepestPaths = array();
    foreach ($array as $path)
    {
        $pathLength = strlen($path);
        // look for all the paths we consider the longest
        // (note how we're using references to the array members)
        foreach ($deepestPaths as &$deepPath)
        {
            $deepPathLength = strlen($deepPath);
            // if $path is prefixed by $deepPath, this means that $path is
            // deeper, so we replace $deepPath with $path
            if (substr($path, 0, $deepPathLength) == $deepPath)
            {
                $deepPath = $path;
                continue 2;
            }
            // otherwise, if $deepPath is prefixed by $path, this means that
            // $path is shallower; so we should stop looking
            else if (substr($deepPath, 0, $pathLength) == $path)
            {
                continue 2;
            }
        }
        // $path matches nothing currently in $deepestPaths, so we should
        // add it to the array
        $deepestPaths[] = $path;
    }
    return $deepestPaths;
}

$paths = array('/a/b', '/a', '/1/2/3/4', '/1/2', '/1/2/3/5', '/a/b/c/d/e');
print_r(getDeepestPaths($paths));

?>

如果您的文件夹名称不以斜杠结尾，您将需要在两个ifs 中进行额外检查：较深路径中前缀旁边的字符是斜杠，因为否则路径 like/foo/bar将被视为“更深的路径”比/foo/b（并将取代它）。

if (substr($path, 0, $deepPathLength) == $deepPath && $path[$deepPathLength] == '/')
if (substr($deepPath, 0, $path) == $path && $deepPath[$path] == '/')

Answer 3

如果您可以保证“拼写”始终相同（即：“/a/bc/d”与 /a/b\ /c/d），那么您应该能够进行一些简单的字符串比较以查看是否其中一个字符串完全包含在另一个字符串中。如果这是真的丢弃字符串。请注意，您需要在两个方向上进行比较。