Ancient Astronaut Theory

 

Ancient Astronaut Theory


You are given a string dictionary, representing a partial  ordering of ancient astronauts' dictionary. Given a string s, return whether it's a lexicographically sorted string according to this ancient astronaut dictionary.

Example 1

Input

dictionary = "acb"
s = "aaaa h ccc i bbb"

Output

true

Explanation

The only constraint is that a comes before c which comes before b .

Example 2

Input

dictionary = "acb"
s = "aaaacccbc"

Output

false

Explanation

This is false because of the last c, which comes after b.



bool solve(string d, string s) {
    unordered_map<char,int>m;
    int i=0;
    for(char c:d){m[c]=i++;}
    string temp="";
    for(auto c:s){
        auto it=m.find(c);
        if(it!=m.end())temp+=to_string(it->second);
    }
    cout<<temp;
    string t=temp;
    sort(t.begin(),t.end());
    return t==temp;
}

Post a Comment

0 Comments