# Sprint 2 Module Project 3
## Isomorphic Strings

"""
Understand

a = "odd"
b = "egg"
output: True ("o" -> "e", "d" -> "g")

a = "oddo"
b = "eggf"
output: False ("o" cannot map to both "e" and "f")

a = "oddh"
b = "egge"
output: False ("o" and "h" cannot both map to "e")

Plan
1. Use a dictionary to keep track of the character mapping from a --> b
2. Whenever you're going to insert a mapping, check if a mapping for
that character already exists.
3. If it already exists and the mapping is not the same, then it can't be isomorphic.
4. If a mapping for that character doesn't yet exist, also check if the character
it's going to be mapped to isn't already mapped by another character (see test case 3)
5. Use a dictionary to track char mapping in a --> b
6. Use a set to track which characters in b have been mapped

Note: I could have used .values() instead of using a set for mappedCharsinB
but that has a slower O(n) runtime for lookup

Runtime: O(length of a or b)
Space: O(length of a or b)
"""

def csIsomorphicStrings(a, b):
    if len(a) != len(b):
        return False
    charMapping = {} # mapping from a->b
    mappedCharsInB = set()
    for i in range(len(a)):
        if a[i] in charMapping: # char in a has already been mapped
            # this char in a doesn't map the same char in b
            # therefore it can't be isomorphic
            if b[i] != charMapping[a[i]]:
                return False
        else: # char in a hasn't been mapped yet
            # check if char in b hasn't been mapped yet
            if not b[i] in mappedCharsInB:
                charMapping[a[i]] = b[i]
                mappedCharsInB.add(b[i])
            else:
                # if char in b has already been mapped, then some other
                # char in a has already been mapped to it
                # therefore it can't be isomorphic
                return False
    return True

## Word Pattern

"""
Understand

pattern = "abba"
a = "dog cat cat dog"
output: True

pattern = "bb"
a = "dog cat"
output: False

pattern = "ab"
a = "dog dog"
output: False

Plan

This is very similar to the last question, but instead of
comparing character->character
we're now comparing character->word

Runtime: O(max(length of pattern, length of a))
Space: O(max(length of pattern, length of a))
"""

def csWordPattern(pattern, a):
    wordList = a.split(' ')

    if len(pattern) != len(wordList):
        return False

    charToWordMapping = {}
    mappedWordsInB = set()
    for i in range(len(pattern)):
        if pattern[i] in charToWordMapping:
            if wordList[i] != charToWordMapping[pattern[i]]:
                return False
        else:
            if not wordList[i] in mappedWordsInB:
                charToWordMapping[pattern[i]] = wordList[i]
                mappedWordsInB.add(wordList[i])
            else:
                return False
    return True

## Group Anagrams

"""
Understand

strs = ["dog", "god", "cat", "act", "lol"]
output = [["dog", "god"], ["cat", "act"], ["lol"]]

strs = ["dog", "cat", "lol"]
output = [["dog"], ["cat"], ["lol"]]

strs = []
output = []

Plan
1. Sort the characters for each string in the list
2. Realize that anagrams will have the same ordering of characters once sorted (e.g. "god" and "dog" when sorted are both "dgo")
3. Group anagrams together by using a dictionary e.g. {"dgo" -> ["god", "dog"]}
4. Get all the values in the dictionary, put them into one array and sort the array based on their
length

Runtime: O(n * klogk + nlogn) where k = length of word, n = length of strs
Space: O(number of elements in strs)
"""
from collections import defaultdict

def csGroupAnagrams(strs):
    anagrams = defaultdict(list)

    for word in strs:
        anagramOrdering = str(sorted(word))
        anagrams[anagramOrdering].append(word)

    res = []
    for (key, words) in anagrams.items():
        res.append(words)

    res.sort(reverse=True, key=len)
    return res