kkanyo / Coding_Test

Study for coding-test
0 stars 0 forks source link

Magic Spells: Do not work correctly about generic spell of some test case #2

Closed kkanyo closed 2 years ago

kkanyo commented 2 years ago

When the generic spells input consecutively, somtimes, result about one of the generic spell is incorrect. However, If only input the it with problem, it works correctly.

else {  // For generic spells
        // find the longest common subsequence using dynamic programming
        string scrollName_ = spell->revealScrollName();
        string journal_ = SpellJournal::read();
        long long scrollNameSize = scrollName_.size();
        long long journalSize = journal_.size();
        int table[journalSize+1][scrollNameSize+1];

        for (int i = 0; i < scrollNameSize; i++) { table[0][i] = 0; }
        for (int i = 0; i < journalSize; i++) { table[i][0] = 0; }

        for (int i = 1; i <= journalSize; i++) {
            for (int j = 1; j <= scrollNameSize; j++) {
                if (journal_[i-1] == scrollName_[j-1]) {
                    table[i][j] = table[i-1][j-1] + 1;
                }
                else { 
                    table[i][j] = max(table[i-1][j], table[i][j-1]);
                }
            }
        }
        cout << table[journalSize][scrollNameSize] << endl;
    }

This code related to find a longest subsequence of letters that are contained in both the spell name and spell journal. I think problem is in this code. Need to find cause of error and optimize that code.

kkanyo commented 2 years ago

Problem code: https://github.com/kkanyo/Coding_Test/blob/master/HackerRank/C%2B%2B/Inheritacne/4-Magic_Spells.cpp