10주차 일요일 1 - LeetCode-Study-Team/solutions GitHub Wiki

구글 코테에서 나온 문제들

1277 Count Square Submatrices with All Ones

  • 특징

    • O(N)으로 끝내자
      • 사각형의 bottom right로 가정
        • 방식: Min(같은행 전열, 전행 같은열, 전행 전열)
        • 의미적으로, 사각형 개수 (or 제일 큰 정사각형 한변 길이)
      • 0행이나 0열은 그대로 두기
  • {0, 1, 1, 1}
{1, 1, 1, 1}
{0, 1, 1, 1}
 
// Final Matrix 값 
{0, 1, 1, 1}
{1, 1, 2, 2}
{0, 1, 2, 3}
public int countSquares(int[][] A) {
    int res = 0;
    for (int row = 0; row < A.length; ++row) {
        for (int col = 0; col < A[0].length; ++col) {
            if (A[row][col] > 0 && row > 0 && col > 0) { // 0행이나 0열은 그대로 두기 
                A[row][col] = Math.min(A[row - 1][col - 1], Math.min(A[row - 1][col], A[row][col - 1])) + 1;
            }
            res += A[row][col];
        }
    }
    return res;
}

1048 Longest String Chain

리트코드 풀이 1 - Bottom-Up DP

  • 특징

    • Input: { "bdca", "a", "b", "bca", "ba", "bda"};
      • 최대 체인: "a", "ba", "bda", "bdca"
    • 풀이
      • bdca 의 가능한 chain을 찾아
        • 예, dca bca bdc

  • Map 결과값

    • {a=1, ab=2, bd=1, abd=3, ac=2, abc=3, abdd=4}

class Solution {
    public int longestStrChain(String[] words) {
        Map<String, Integer> dp = new HashMap<>();
        Arrays.sort(words, (a, b) -> a.length() - b.length());

        int longestWordSequenceLength = 1;

        for (String word : words) {
            int presentLength = 1;
            // letter 하나씩 제거하며 가능한 모든 단어 찾기 
            for (int i = 0; i < word.length(); i++) {
                StringBuilder sb = new StringBuilder(word);
                sb.deleteCharAt(i);
                int previousLength = dp.getOrDefault(sb.toString(), 0);
                presentLength = Math.max(presentLength, previousLength + 1);
            }
            dp.put(word, presentLength);
            longestWordSequenceLength = Math.max(longestWordSequenceLength, presentLength);
        }
        return longestWordSequenceLength;
    }
}

리트코드 풀이 2 - Top-Down DP (Recursion + Memoization)

  • ['abcd','abc','bcd','abd','ab','ad','b']
public int longestStrChain(String[] words) {
    Map<String, Integer> memo = new HashMap<>();
    Set<String> wordsPresent = new HashSet<>();
    Collections.addAll(wordsPresent, words);
    int ans = 0;
    for (String word : words) { 
        ans = Math.max(ans, dfs(wordsPresent, memo, word));
    }
    return ans;
}

private int dfs(Set<String> wordSet, Map<String, Integer> memo, String currentWord) {
    // DP 장점 활용: 최대 체인값 map에서 찾아오기 
    if (memo.containsKey(currentWord)) {
        return memo.get(currentWord);
    }

    int maxLength = 1; // 현재 단어의 최대 chain 
    StringBuilder sb = new StringBuilder(currentWord);

    // 가능한 모든 chain string 만들기 
    for (int i = 0; i < currentWord.length(); i++) {
        sb.deleteCharAt(i);
        String newWord = sb.toString();
        
        // 주어진 단어 set 중 하나면, 다시 그 단어의 최대 체인 가져오기 위해 DFS 
        if (wordSet.contains(newWord)) {
            maxLength = Math.max(maxLength, 1 + dfs(wordSet, memo, newWord));
        }
        sb.insert(i, currentWord.charAt(i));
    }
    memo.put(currentWord, maxLength);

    return maxLength;
}

내풀이

  • [ "a", "b" ,"ba", "bca", "bda", "bdca" ]
class Solution {
    public int longestStrChain(String[] words) {
        Arrays.sort(words, ((o1, o2) -> o1.length() - o2.length()));
        int[] dp = new int[words.length];
        dp[0] = 1;
        helper(words, dp, 0);
        return IntStream.of(dp).max().orElse(0);
    }

    private void helper(String[] words, int[] dp, int start) {
        if (start >= words.length) return;
        dp[start] = Math.max(1, dp[start]);
        for (int i = start; i < words.length; i++) {
            // 추가하기: if words[i].length > words[start].lenght stop exploration 
            if (isChain(words[start], words[i])) {
                dp[i] = Math.max(dp[start] + 1, dp[i]);
            }
        }

        helper(words, dp, start + 1);
    }


    private boolean isChain(String left, String right) {
        if (left.length() < right.length() - 1 || left.length() == right.length()) return false;

        int i = 0;
        int mismatchCount = 0;
        for (char rightC : right.toCharArray()) {
            if (i == left.length()) return true;
            if (rightC == left.charAt(i)) {
                i++;
                continue;
            }
            mismatchCount++;
            if (mismatchCount >= 2) { // 2개 이상 다르면 chain 아님
                return false;
            }
        }
        return true;
    }
}
⚠️ **GitHub.com Fallback** ⚠️