문제 링크

내 코드

3ms, 17.11MB

class Solution {
public:
    bool canMakeSubsequence(string str1, string str2) {
        int s2{}, e2 = static_cast<int>(str2.length());

        for(int i{}, e{static_cast<int>(str1.length())}; i < e; ++i ) {
            if(str1[i] == str2[s2] || ((str1[i] - 'a' + 1) % 26) == str2[s2] - 'a') {
                ++s2;
                if(s2 == e2) break;
            }
        }
        if(s2 == e2) return true;
        else return false;
    }
};

Solution

Approach 1: Brute Force (Time Limit Exceeded)

• Time Limit Exceeded
• Complexity
  • Let $n$ be the length of the string str1 and $m$ be the length of the string str2.
  • Time Complexity: $O(2^n \cdot n \cdot m)$
  • Space Complexity: $O(n)$

class Solution {
public:
    bool canMakeSubsequence(string str1, string str2) {
        int lengthStr1 = str1.length();

        // Try all possible combinations of character increments
        for (int mask = 0; mask < (1 << lengthStr1); mask++) {
            string temp = str1;

            // Apply increments based on current mask
            for (int str1Index = 0; str1Index < lengthStr1; str1Index++) {
                if (mask & (1 << str1Index)) {
                    temp[str1Index] = getNextChar(temp[str1Index]);
                }
            }

            // Check if str2 is a subsequence of the modified string
            if (isSubsequence(temp, str2)) {
                return true;
            }
        }

        return false;
    }

private:
    // Helper function to get the next character cyclically
    char getNextChar(char str1Char) {
        return str1Char == 'z' ? 'a' : str1Char + 1;
    }

    // Helper function to check if str2 is a subsequence of str1
    bool isSubsequence(string& str1, string& str2) {
        int str1Index = 0, str2Index = 0;
        int lengthStr1 = str1.size(), lengthStr2 = str2.size();

        // Traverse through both strings using a while loop
        while (str1Index < lengthStr1 && str2Index < lengthStr2) {
            if (str1[str1Index] == str2[str2Index]) {
                str2Index++;
            }
            str1Index++;
        }
        // Check if all characters in str2 were matched
        return str2Index == lengthStr2;
    }
};

Approach 2: Optimized Single Pass (Two Pointer)

• 10ms, 17.07MB
• Complexity
  • Let $n$ be the length of the string str1 and $m$ be the length of the string str2.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(1)$

class Solution {
public:
    bool canMakeSubsequence(string str1, string str2) {
        int str2Index = 0;
        int lengthStr1 = str1.size(), lengthStr2 = str2.size();

        // Traverse through both strings using a for loop
        for (int str1Index = 0;
             str1Index < lengthStr1 && str2Index < lengthStr2; ++str1Index) {
            // Check if characters match, or if str1[str1Index] can be
            // incremented to str2[str2Index]
            if (str1[str1Index] == str2[str2Index] ||
                (str1[str1Index] + 1 == str2[str2Index]) ||
                (str1[str1Index] - 25 == str2[str2Index])) {
                // If match found, move to next character in str2
                str2Index++;
            }
        }
        // Check if all characters in str2 were matched
        return str2Index == lengthStr2;
    }
};