Ancient Astronaut Theory

 

Ancient Astronaut Theory

You are given a string dictionary, representing a partial lexicographic 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;

}