My code has a bug but the OJ gives me AC


  • 0
    C

    For input "aaaaaaaa", ["aa", "aa", "aa"] the correct answer should be [0, 1, 2]. But my code gives [0, 2] and the OJ produces AC. I'll appreciate it if you can add the test case.

    Here's my code.

    vector<int> findSubstring(string S, vector<string> &L) {
        if (L.empty() || S.length() < L[0].length()) {
            return {};
        }
        vector<int> result;
        int wordLen = (int)L[0].length();
        unordered_map<string, int> dict;
        unordered_map<string, int> count;
        for (auto & word : L) {
            dict[word]++;
        }
        int start = 0, n = 0;
        int maxStart = (int)S.length() - wordLen * (int)L.size();
        for (int i = 0; start <= maxStart;) {
            string seg = S.substr(i, wordLen);
            if (dict.find(seg) == dict.end()) {
                i = ++start;
                n = 0;
                count.clear();
            } else {
                if (count[seg] < dict[seg]) {
                    n++;
                } else {
                    string tmp;
                    while (n > 0 && (tmp = S.substr(start, wordLen)) != seg) {
                        count[tmp]--;
                        start += wordLen;
                        n--;
                    }
                    start += wordLen;
                }
                count[seg]++;
                if (n == L.size()) {
                    result.push_back(start);
                }
                i += wordLen;
            }
        }
        return result;
    }

  • 0

    Thanks for your test case. I have added your test case and your code now get Wrong Answer.


  • 0
    C

    Thank you so much:)


Log in to reply
 

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