Is the set of test cases complete?


  • 1
    K

    Hello!
    When testing my own solution using the online judge, I found that one important test case might not be covered by the current set of test cases. My solution (which is pasted at the end of this post) can pass the online judge, but not the test case below.

    S = "aabbaabbaabb";
    L = {"bb","aa","bb","aa","bb"};

    In the above test case, the returned vector should only contain index '2', but my code returns nothing. This observation implies that the acceptance of the online judge doesn't necessary guarantee the correctness of a solution.

    Below is my solution (Please bear with the ugly code). Here is some important explanation. In my code, I commented out two lines 17 and 19. Without these two lines, hash table idxHT always records the last location of the current word S.substr(idx, l). In the above case, when processing the third 'aa' in S, the returned index will be 6, which is the index of the second 'bb', leading an empty vector to be returned. After putting lines 17 and 19 back, the hash table idxHT only records the index of the first appearance of a qualified word, and thus the function isMatched() will return 2, instead of 6, which will result in a correct returned vector.

    In summary, the issue is that the problematic solution below can pass the current online judge due to the missing test case mentioned above.

    class Solution {
    public:
        bool isMatched(string S, int idx, int l, int m, unordered_map<string, int> &HT, int &retIdx) {
            int origIdx = idx;
            unordered_map<string, int> newHT = HT;
            unordered_map<string, int> idxHT;
            while (m > 0) {
                if (newHT.find(S.substr(idx, l)) == newHT.end()) {
                    retIdx = idx + l;
                    return false;
                } else {
                    if (newHT[S.substr(idx, l)] == 0) {
                        retIdx = idxHT[S.substr(idx, l)] + l;
                        return false;
                    } else {
                        newHT[S.substr(idx, l)]--;
                        //if (idxHT.find(S.substr(idx,l)) == idxHT.end()) {
                            idxHT[S.substr(idx, l)] = idx;      // !!! without the surrounding 'if', this line records the last position of word S.substr(idx, l). 
                        //}
                        idx += l;
                        m--;
                        if (m == 0) {
                            retIdx = origIdx + l;
                            return true;
                        }
                    }
                }
            }
            assert(false);
            return true;
        }
        vector<int> findSubstring(string S, vector<string> &L) {
            vector<int> v;
            if (S.size() == 0 || S.size() < L.size() * L[0].size()) return v;
            
            unordered_map<string, int> HT;
            for (int i = 0; i < L.size(); i++) {
                if (HT.find(L[i]) == HT.end()) {
                    HT[L[i]] = 0;
                }
                HT[L[i]]++;
            }
            
            int n = S.size(), m = L.size(), l = L[0].size();
            for (int j = 0; j < l; j++) {
                bool prev = false;
                bool isFirst = true;
                for (int i = j; i <= n - m * l; ) {
                    if (isFirst) {
                        isFirst = false;
                        int retIdx = 0;
                        if (isMatched(S, i, l, m, HT, retIdx)) {
                            v.push_back(i);
                            prev = true;
                        }
                        i = retIdx;
                    } else {
                        if (prev == true) {
                            if (S.substr(i - l, l) == S.substr(i + (m - 1) * l, l)) {
                                v.push_back(i);
                                prev = true;
                                i += l;
                            } else if (HT.find(S.substr(i + (m - 1) * l, l)) == HT.end()) {
                                prev = false;
                                i += m * l;
                            } else {  // HT.find(S.substr(i + (m - 1) * l, l)) != HT.end()
                                int retIdx = 0;
                                if (isMatched(S, i, l, m, HT, retIdx)) {
                                    v.push_back(i);
                                    prev = true;
                                } else {
                                    prev = false;
                                }
                                i = retIdx; 
                            }
                        } else {
                            int retIdx = 0;
                            if (isMatched(S, i, l, m, HT, retIdx)) {
                                v.push_back(i);
                                prev = true;
                            }
                            i = retIdx;
                        }
                    }
                }
            }
            return v;
        }
    };

  • 0

    Thanks! I've added your test case, and now code gets Wrong Answer.


Log in to reply
 

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