Java recursion: how to pass a String

Question

I am examining this code problem:

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'
}

The accepted solution is below (please note this is pseudocode only).

I want to implement it in 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)
      }
  }
}

My doubt is at the the arrow.

We recursively pass to the flattenDictionary() method a new String each time by concatenating the initialKey with the new keythat we got from the Map.

Here we are potentially creating many long Strings!

Is it possible to avoid creating all those Strings?

I don't think that passing StringBuilder could be a solution, because we would end up with wrong results

Answer 1

You can use a StringBuilder if you undo your changes after the recursive call. Assuming initialKey is now an instance of StringBuilder, you can do something like this:

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

flattenDictionary(initialKey, value, flatDictionary)

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