A possible solution regarding to "t is very long" and the follow up "lots of incoming S"


  • 4
    S

    I think this basic idea is to reuse string T and make the complexity of each query of S mainly dominated by the length of S. Here is the summary of my solution:

    1. We record the position indexs of every letter appearing in T separately and naturally in ascending order. (This only need to be done once for multiple queries.)
    2. For an incoming S, we iterate through every char in S. For char S[i], we go to its position index list and see if we can find a feasible index, i.e., a position that is beyond the position chose for S[i-1] (maintained by endPos). If yes, we update endPos and move to S[i+1]; otherwise, we fail.
    3. Further improvement: We can accelerate the creation of index lists from T by using paralleling processing. Every machine is responsible for a part of T and generate a paritial index lists. After all machines finish, we merge those partial index lists together, which is actually easy.

    Here is the code:

    public class Solution {
        // Position index list for each letter appearing in t. 
        // These lists can be reused for multiple queries with different input string s.
        List<List<Integer>> charIndexLists = new ArrayList<List<Integer>>();
        
        public boolean isSubsequence(String s, String t) {
            // Create position index list for each letter in t.
            // IMPORTANT: This part only need to be done ONCE for multiple queries.
            for (int i=0;i<26;i++){
                charIndexLists.add(new ArrayList<Integer>());
            }
            char[] tCharArr = t.toCharArray();
            for (int i=0;i<t.length();i++){
                charIndexLists.get(tCharArr[i]-'a').add(i);
            }
            
            // Check if we can find a feasible sequence of indexs in charIndexLists mathcing to s.
            char[] sCharArr = s.toCharArray();
            int[] pLists = new int[26];
            int endPos = -1;
            for (int i=0;i<s.length();i++){
                // Find out the next available position of current char, i.e., 
                // sCharArr[i] should appeear somewhere after endPos. 
                int curIndex = sCharArr[i]-'a';
                List<Integer> curIndexList = charIndexLists.get(curIndex);
                while (pLists[curIndex] < curIndexList.size() && curIndexList.get(pLists[curIndex]) <= endPos){
                    pLists[curIndex]++;
                }
                // Cannot find any required char that appears after endPos, fails
                if (pLists[curIndex] == curIndexList.size()){
                    return false;
                }
                // Update endPos.
                endPos = curIndexList.get(pLists[curIndex]);
            }
            return true;
        }
    }

  • 0

    @shili30205 Same idea as my 1st attempt, the inner while loop can be convert to a binary search, which is more efficient.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.