# CSPT23 Lecture 7
## [Jewels and Stones](https://leetcode.com/problems/jewels-and-stones/)

class Solution:
    """
    jewels = "aA", stones = "aAAbbbb"
    output = 3
    
    jewels = "z", stones = "ZZ"
    output = 0
    
    jewels = "z", stones = "zzz"
    output = 3
    
    jewels = "", stones = "abc"
    output = 0
    
    jewels = "z", stones = ""
    output = 0
    
    Plan
    Brute-force solution
    For each stone, iterate over jewels to see if it's a jewel. Keep a running counter of how many
    jewels you find.
    
    Dictionary
    Define a dictionary with jewels as the key and instantiate each value as 0. Then iterate through the list of stones and if stones in dictionary then increase the corresponding key by 1 else continue. Finally iterate through each key and keep adding the values until the last key. return the total sum.
    
    Set
    Put all the jewels in a set. Then go through each stone and see if that stone is in the set. Keep a counter to count how many stones are jewels.
    """
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        j = set(jewels)
        count = 0
        for stone in stones:
            if stone in j:
                count += 1
        return count
    
    def numJewelsInStonesDictionary(self, jewels: str, stones: str) -> int:
        jewelCount = {} # jewels --> num stones
        for jewel in jewels:
            jewelCount[jewel] = 0
        
        for stone in stones:
            if stone in jewelCount:
                jewelCount[stone] += 1
        
        totalCount = 0
        for _, count in jewelCount.items():
            totalCount += count
        return totalCount
        

## [Smaller than Number](https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/)

class Solution:
    """
    nums = [8,1,2,2,3]
    output = [4,0,1,1,3]
    
    nums = [6,5,4,8]
    output = [2,1,0,3]
    
    nums = [7,7,7,7]
    output = [0,0,0,0]
    
    Brute-force
    For each num, look at all the other nums and see how many other nums are less than it
    Just append the count to the resulting list
    
    Dictionary
    nums = [8,1,2,2,3]
    sortedNums = [1,2,2,3,8*]
    numMap = {1: 0, 2: 1, 3: 3, 8: 4}
    [4, 0, 1, 1, 3]
    """
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        sortedNums = sorted(nums)
        numMap = {}
        for i, num in enumerate(sortedNums):
            if num not in numMap:
                numMap[num] = i
        res = []
        for num in nums:
            res.append(numMap[num])
        return res

## [Keyboard Row](https://leetcode.com/problems/keyboard-row/submissions/)

class Solution:
    """
    words = ["Hello","Alaska","Dad","Peace"]
    output = ["Alaska","Dad"]

    words = ["Hello",Peace"]
    output = []
    
    words = ["ALaskA","DAd"]
    output = ["Alaska","Dad"]
    
    words = ["ALaskA","pop"]
    output = ["Alaska","pop"]
    
    For word in words
        Take a look at the first character of the string and find out which row that character belongs in (make sure to convert the char to lowercase)
        Now check all the other characters in that string, if all those characters are in that set then it can be typed in the same row. Add that to the
        resulting list
        
    Assume that a word is no longer than k characters
    Assume that the length of words is n
    Runtime: Upper-bound by k * n
    Space: O(n) where n = length of words
    """
    def findWords(self, words: List[str]) -> List[str]:
        rows = [set(["q","w","e","r","t","y","u","i","o","p"]), set(["a","s","d","f","g","h","j","k","l"]), set(["z","x","c","v","b","n","m"])]
        res = []
        
        for word in words:
            rowFirstLetterBelongsTo = set()
            for row in rows:
                if word[0].lower() in row:
                    rowFirstLetterBelongsTo = row
                    break
            
            allLettersAreInSameRow = True
            for i in range(1, len(word)):
                if word[i].lower() not in rowFirstLetterBelongsTo:
                    allLettersAreInSameRow = False
                    break
            
            if allLettersAreInSameRow:
                res.append(word)
        return res