Reputation: 8113
My question is:
ArrayList<String> temp = new ArrayList<String>(r);
Without this line, I am inserting nothing into res
why?
Why without copying r
into a new temp ArrayList
, I am copying nothing to res
?
public class Solution {
public ArrayList<ArrayList<String>> partition(String s) {
ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
ArrayList<String> r = new ArrayList<String>();
find(s, 0, r, res);
return res;
}
private void find(String s, int st, ArrayList<String> r, ArrayList<ArrayList<String>> res) {
if (st >= s.length()){
// This seems important. Without the next line, I am inserting
// nothing into "res". Why?
ArrayList<String> temp = new ArrayList<String>(r);
res.add(temp);
return;
} else {
for (int i=st; i<s.length();i++) {
if (isValid(s, st, i)) {
r.add(s.substring(st,i+1));
find(s, i + 1, r, res);
r.remove(r.size()-1);
}
}
}
}
private boolean isValid(String s, int st, int end) {
while (st < end) {
if (s.charAt(st) != s.charAt(end)) {
return false;
}
st++;
end--;
}
return true;
}
}
Upvotes: 0
Views: 125
Reputation: 1199
You need this line because you remove added item to r
after find
:
r.add(s.substring(st,i+1));
find(s, i + 1, r, res);
r.remove(r.size()-1); // <<<<<< HERE
so when you add just r
to res
without real copy you remove line not only from r
but from res
as well =)
Upvotes: 0
Reputation: 34648
As the other answer said, doing:
res.add(r)
Adds a reference to the same object r
is referring to, into the list. Effectively, what happens here is:
r
refers to a listadd
res
But notice that both r
and the reference inside res
are referring to the same object
When you do the thing with the temp
what happens is:
r
.temp
add
res
So now r
points to the original copy of the list, and the reference inside res
points to the new copy of it. They are two distinct objects.
Why is this important?
Basically, your recursive step adds one element to r
, calls find
again, and then removes one element from r
. The reference in r
and res
are passed down the recursion so it means those two same objects are passed down the recursion.
But since after you return from the recursion, you actively remove one object from r
, it means that at the end, when you go all the way up, there will be no more elements inside r
.
Since the reference stored inside res
is pointing to the same object r
is pointing to, not to a copy of it, it means that when you remove an item using r.remove()
, that object becomes empty. But that's the same object that we are referring to from inside res
. So at the end of the recursion, it will be empty.
Think of it like a safe. Person A fills the safe with money. Then he gives person B a second key to the safe. Then he goes in with his original key, and takes out all the money. When B comes and opens the safe, it is empty!
Copying the list is the equivalent of A giving B his own money to put in his own safe. A can remove as much money as he wants from his own safe, and it won't change the amount of money in B's safe.
Upvotes: 1
Reputation: 3574
By doing this:
res.add(r);
you store the input list in the result list of lists. If you modify the input list afterwards, those changes will also appear in the entry of res
, since it is the same list.
ArrayList<String> temp = new ArrayList<String>(r);
res.add(temp);
This, however, copies the current contents of the input list r
into a new list, and saves this new list in the result list res
.
The difference is, that you don't store the whole input list, but its current entries. So even if the input list changes afterwards, it won't affect the list saved in your res
list, because res
will only contain "snapshots" of the input lists, at the time the method was called.
There are two concepts of passing data that are called "pass by value" and "pass by reference". Java is always "pass by value", but that does not mean, that all fields of the object are just copied from one place to another one. The address of that object is passed by value to the new field. Read this post for a more detailed explanation about this: https://stackoverflow.com/a/40523/2324078
Upvotes: 0