[Mock] Amazon

1160. Find Words That Can Be Formed by Characters

You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

My Answer 1: Accepted (Runtime: 124 ms - 73.19% / Memory Usage: 14.8 MB - 31.44%)

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        count = 0
        strcnt = collections.Counter(chars)
        
        for i in range(len(words)):
            temp = 0
            
            if len(words[i]) > len(chars):
                continue
            
            wrdcnt = collections.Counter(words[i])
            
            for j in range(len(words[i])):
                if wrdcnt[words[i][j]] <= strcnt[words[i][j]]:
                    temp += 1
                else:
                    break
            
            if temp == sum(wrdcnt.values()):
                count += len(words[i])
        
        return count

문제를 잘못 이해해서 허탕을 40분간 치다가... 막판 5분에 제대로 이해 완.

chars 에 있는 단어들로 구성된 words[i] 만 고르는 거 였다.

---

1155. Number of Dice Rolls With Target Sum

You have d dice, and each die has f faces numbered 1, 2, ..., f.

Return the number of possible ways (out of fd total ways) modulo 10^9 + 7 to roll the dice so the sum of the face up numbers equals target.

My Answer 1: Wrong Answer (38 / 65 test cases passed.)

class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        if target > d*f:
            return 0
        
        if target < f:
            return 1
        
        count = 0
        
        for i in range(1, d):
            for j in range(1, f+1):
                # 0 ~ f 사이면
                if target - j > 0 and target - j <= f:
                    count += 1
        
        return count

이 문제에는 집중을 잘 못했네요

Solution 1: Accepted (Runtime: 196 ms - 84.96% / Memory Usage: 15.3 MB - 49.62%)

class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        dp = {}
        def r_roll(dice, target):
            if target>f*dice:
                dp[dice, target] = 0
                return 0
            if dice == 0: return target==0
            if target <0: return 0
            if (dice, target) in dp: return dp[dice, target]
            ways = 0
            for num in range(1, f+1):
                ways+=r_roll(dice-1, target-num)
            dp[dice, target] = ways
            return ways
        return r_roll(d, target)%(10**9+7)

dp 사용