0

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... Error in commenting out "arr[c-'a']=new ArrayList();"

Edit: updated the code and input data set to see the error.

Improve this question
0

4 Answers 4

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

I have already initiated it in ``` for(int i=0; i<26; i++) arr[i]=new ArrayList<>();``` and calculated the arr[i]. Why I need to initiate there again?
In another way to ask this question is what is different between List<Queue<Character>> list=arr[c-'a']; arr[c-'a']=new ArrayList(); and List<Queue<Character>> list=new ArrayList(arr[c-'a']);
The second one creates a copy of the list, the first one creates an empty list. For a large list, copying will have a severe performance impact.
1

"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

Improve this answer

4 Comments

This may be what I look for - 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.
Both "arr[c-'a']=new ArrayList();" and "List<Queue> list=new ArrayList(arr[c-'a']);" will return 3 correctly. Why does "List<Queue> list=new ArrayList(arr[c-'a']);" not have a looping issue?
Because "List<Queue> list=new ArrayList(arr[c-'a']);" will create a new ArrayList, the loop below will traverse the new ArrayList and add Queue to the old ArrayList. There are two ArrayList, you use an enhanced for loop to traverse the new ArrayList and add element to the old one, it will not occur the ConcurrentModificationException.
This algorithm requires removing the old value from the arr. If you use "List<Queue> list=new ArrayList(arr[c-'a']);", when the String s has a same character, it will return a larger value than the original code.
1

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.

Improve this answer

Comments

0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.