I do not understand line "arr[c-'a']=new ArrayList();" in code below. Without it, the code does not work.
Replacing
List<Queue<Character>> list=arr[c-'a'];
arr[c-'a']=new ArrayList();
with
List<Queue<Character>> list=new ArrayList(arr[c-'a']);
can work. But it will have performance issue in large data set.
What "arr[c-'a']=new ArrayList();" does?
//Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s.
package test.Test;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
class Test
{
int MatchingSubseq(String s, String[] words) {
List<Queue<Character>>[] arr=new ArrayList[26];
for(int i=0; i<26; i )
arr[i]=new ArrayList<>();
for(String w:words){
Queue<Character> que=new ArrayDeque<>();
for(var c:w.toCharArray()){
que.add(c);
}
arr[que.peek()-'a'].add(que);
}
int res=0;
for(char c:s.toCharArray()){
List<Queue<Character>> list=arr[c-'a'];
arr[c-'a']=new ArrayList();
for(Queue<Character> q:list){
q.poll();
//System.out.println(q);
if(q.size()==0)
res ;
else
arr[q.peek()-'a'].add(q);
}
}
return res;
}
// Driver Program
public static void main(String[] args)
{
String s = "abcde";
String[] words = {"a","bb","acd","ace"};
Test test=new Test();
System.out.println(test.MatchingSubseq(s, words));
}
}
Edit: if comment out "arr[c-'a']=new ArrayList();", I will see the error as below. It only happens in some online compilers. Strange...
Edit: updated the code and input data set to see the error.
CodePudding user response:
The question is, what does the code below do:
arr[c-'a'] = new ArrayList();
It assigns a new ArrayList
at index c - 97
in array arr
, 97
being the int
value of the char
with value 'a'
.
This logic is used to be able to access an array using values a-z
by converting them to indexes 0-25
, making use of the fact that char
is implicitly a numerical data type (16 bit unsigned integer) in Java.
CodePudding user response:
In your code, c
is a char variable, c - 'a'
is calculating the difference between the value of char in variable c
and 'a'
.
So with arr[c-'a']
, you are assigning the entry on that c - 'a'
index of the array.
CodePudding user response:
You've got an array there with 26 entries, which are numbered from 0 to 25.
But you're using that array to store information for each character from 'a'
to 'z'
. So for each character, you need to convert the letter ('a'-'z'
) to a number 0-25, to be able to find it in the array.
The simplest way to convert 'a'
to 0, 'b'
to 1 and so on, up to converting 'z'
to 25, is to subtract the value 'a'
. This works because 'a'
actually has a numeric value, but you don't need to know that value in order to write code where 'a'
gets subtracted.
CodePudding user response:
"arr[c-'a']=new ArrayList();" is like to use a new ArrayList to replace the old one. If you comment out it, the old ArrayList will still in the arr[c-'a']. In some cases, such as "bb", "arr[q.peek()-'a'].add(q);" will add a Queue to the ArrayList that is looping and it will throw the ConcurrentModificationException.
"List<Queue> list=new ArrayList(arr[c-'a']);" is only create a copy of old ArrayList, so it will not cause the ConcurrentModificationException in the loop, but the old Queue what you should remove still in the list. Therefore the final result may larger than your except. Such as
String s = "abbcde";
String[] words = {"a","bb","acd","ace", "bz"};
"arr[c-'a']=new ArrayList();" will return 4 but "List<Queue> list=new ArrayList(arr[c-'a']);" will return 6