Java 递归 : how to pass a String

Question

我正在检查这个代码问题:

Given a dictionary, write a function to flatten it.

Consider the following input/output scenario for better understanding:

Input:

{
  'Key1': '1',
  'Key2': {
    'a' : '2',
    'b' : '3',
    'c' : {
      'd' : '3',
      'e' : '1'
      }
    }
}

Output:
{
  'Key1': '1',
  'Key2.a': '2',
  'Key2.b' : '3',
  'Key2.c.d' : '3',
  'Key2.c.e' : '1'
}

可接受的解决方案如下(请注意这只是伪代码)。

我想用Java实现

function flattenDictionary(String initialKey, dictionary, flatDictionary){

  for (key : dictionary.keyset()){
      value = dictionary.get(key)

      if (!isHashMapInstance(value)){ 
          if (initialKey == null || initialKey == "")
              flatDictionary.put(key, value)
          else
              flatDictionary.put(initialKey + "." + key, value)             
      }
      else { 
        if (initialKey == null || initialKey == "")
          flattenDictionary(key, value, flatDictionary)
        else
          //-----> Here we are creating a new String for each recursive call !!!!<----
          flattenDictionary(initialKey + "." + key, value, flatDictionary)
      }
  }
}

我的疑问在于箭头。

我们通过将 initialKey 与我们从 map 。

这里我们可能会创建许多长字符串!

是否可以避免创建所有这些字符串？

我认为传递 StringBuilder 不是解决方案，因为我们最终会得到错误的结果

Answer 1

如果您在递归调用后撤消您的更改，则可以使用 StringBuilder。假设 initialKey 现在是 StringBuilder 的一个实例，您可以这样做:

int originalLength = initialKey.length()
initialKey.append(".").append(key)

flattenDictionary(initialKey, value, flatDictionary)

initialKey.setLength(originalLength) // undo: delete the appended chars