'2025/05/16'에 해당되는 글 1건

Leetcode Problem:

• Longest Unequal Adjacent Groups Subsequence II

Summary

• Given a string array and an array of groups, find the longest subsequence of indices such that for each pair of adjacent indices in the subsequence, their corresponding groups are unequal and the hamming distance between the strings is 1.

Approach

• Dynamic programming and backtracking are used to solve the problem
• The dynamic programming table dp is used to store the length of the longest subsequence ending at each index, and the previous table prev is used to store the previous index in the longest subsequence
• The check function is used to calculate the hamming distance between two strings.

Complexity

• O(n^2) where n is the length of the input arrays, due to the nested loops in the dynamic programming table construction and the backtracking phase.

Solution Code:

class Solution {
public:
    vector getWordsInLongestSubsequence(vector& words,
                                                vector& groups) {
        int n = groups.size();
        vector dp(n, 1);
        vector prev(n, -1);
        int maxIndex = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (check(words[i], words[j]) == 1 && dp[j] + 1 > dp[i] &&
                    groups[i] != groups[j]) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
            if (dp[i] > dp[maxIndex]) {
                maxIndex = i;
            }
        }

        vector ans;
        for (int i = maxIndex; i >= 0; i = prev[i]) {
            ans.emplace_back(words[i]);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }

    bool check(string& s1, string& s2) {
        if (s1.size() != s2.size()) {
            return false;
        }
        int diff = 0;
        for (int i = 0; i < s1.size(); i++) {
            diff += s1[i] != s2[i];
            if (diff > 1) {
                return false;
            }
        }
        return diff == 1;
    }
};