BinarySearch 0235 Ancient Astronaut Theory

Problem statement

https://binarysearch.com/problems/Ancient-Astronaut-Theory/

Solution

Not very clear statement. In fact what we need to do is to:

1. Find all symbols in s, which are in dictionary and do not care about all others.
2. Check that order of these symbols are correct: it means that for each adjacent pair we have them in correct order.

Complexity

It is O(n) for time and O(26) for space.

Code

class Solution:
    def solve(self, dictionary, s):
        ord_d = {l:i for i, l in enumerate(dictionary)}
        symbs = [i for i in s if i in ord_d]
        for i, j in zip(symbs, symbs[1:]):
            if ord_d[i] > ord_d[j]: return False
            
        return True