javascript - 搜索 JSON 中的最长路径

Question

我想知道是否有一种快速方法可以找到在下面的 JSON 中获取最长路径的解决方案。结果应为 4 或 ["Phnom Penh"、"Doun Penh"、"Phsa Thmey"、"Phsa Thmey One"]

{
"name": "Phnom Penh",
"code": "PP",
"sub": [
    {
        "name": "Reousey Keo",
        "code": "RK",
        "sub": {
            "name": "Toul Sangke",
            "code": "TSK"
        }
    },
    {
        "name": "Doun Penh",
        "code": "DP",
        "sub": {
            "name": "Phsa Thmey",
            "code": "PT",
            "sub": {
                "name": "Phsa Thmey One",
                "code": "PTO"
            }
        }
    },
    {
        "name": "Mean Chey",
        "code": "MC",
        "sub": {
            "name": "Nerot",
            "code": "NR"
        }
    }
    ]
},
{
    "name": "Kandal",
    "code": "KD"
}

Answer 1

这种递归方法应该适用于任何数组和哈希的嵌套(尽管我怀疑它可以简化一些)。这里我假设键 :sub 没有什么特别的，因此代码可以与(例如)片段一起使用:

{
  name: "Doun Penh",
  code: "DP",
  hub: {
    name: "Toledo" }
    code: "TOL"
  }
  bub: {
    name: "Phsa Thmey",
    code: "PT",
    dub: {
      name: "Phsa Thmey One",
      code: "PTO"
    }
  }
}

下面的代码对由 JSON 字符串构造的数组进行操作。

代码

def deepest(obj, key, dsf={ depth: 0, path: [] })
  dsf_below = dsf.dup
  case obj
  when Array
   obj.each_with_index do |o,i|
     d = deepest(o, key, { depth: dsf[:depth], path: dsf[:path] + [i] } )
     if d[:depth] > dsf_below[:depth]
       dsf_below = d
     end
   end
  when Hash
   if obj.key?(key)
     dkey = { depth: dsf[:depth]+1, path: dsf[:path] + [obj[key]] }
     if dkey[:depth] > dsf_below[:depth]
       dsf_below = dkey
     end
     obj.each do |k,v|
       if (v.is_a? Array) || (v.is_a? Hash)
         d = deepest(v, key, { depth: dkey[:depth], path: dkey[:path] + [k] } )
         if d[:depth] > dsf_below[:depth]
           dsf_below = d
         end
       end
     end
   end
  end
  dsf_below
end

示例

arr = [
  {
    name: "Phnom Penh",
    code: "PP",
    sub: [
      { 
        name: "Reousey Keo",
        code: "RK",
        dub: {
          name: "Toul Sangke",
          code: "TSK" } },
      {
        name: "Doun Penh",
        code: "DP",
        bub: {
          name: "Phsa Thmey",
          code: "PT",
          gub: {
            name: "Phsa Thmey One",
            code: "PTO" } } },
      {
        name: "Mean Chey",
        code: "MC",
        hub: {
          name: "Nerot",
          code: "NR" } } ] },
  {
    name: "Kandal",
    code: "KD" } ]

deepest(arr, :name)
  #=> {:depth=>4, :path=>[0, "Phnom Penh", :sub, 1, "Doun Penh",
  #    :bub, "Phsa Thmey", :gub, "Phsa Thmey One"]}