At a remote weather relay, sentries transmit short callsigns spelled only with lowercase English letters. Each relay station uses its own custom cipher order — a scrambled ranking of the 26 letters — to decide which callsigns should be logged before others. You are given the station's cipher order and the sequence of callsigns exactly as they arrived. Determine whether the callsigns arrived in non-decreasing order according to the station's cipher, using the cipher's letter ranks in place of the usual alphabetical ranks. When one callsign is an exact prefix of the next, the shorter one is considered smaller (comes first), exactly like ordinary dictionary order but with cipher-based letter ranks.
Line 1: a string of length 26, a permutation of the lowercase letters 'a' through 'z', listing them from lowest cipher rank to highest (the first character has the lowest rank). Line 2: an integer n, the number of callsigns. Next n lines: each line is one callsign, a non-empty string of lowercase English letters.
Print "YES" if the callsigns appear in non-decreasing order under the cipher, otherwise print "NO".
1 <= n <= 100. 1 <= length of each callsign <= 20. The cipher-order string is always a permutation of 'a' to 'z'. Callsigns contain only lowercase English letters.
Example 1
Input
bacdefghijklmnopqrstuvwxyz 3 bat cat dog
Expected
YES
Explanation
The cipher ranks letters as b < a < c < d < e < ... < z. Comparing first letters: 'b' (rank 0) < 'c' (rank 2) so "bat" precedes "cat"; 'c' (rank 2) < 'd' (rank 3) so "cat" precedes "dog". The sequence is non-decreasing under the cipher, so the answer is YES.
Example 2
Input
abcdefghijklmnopqrstuvwxyz 3 apple app apples
Expected
NO
Explanation
Here the cipher is the ordinary alphabet. "app" is a prefix of "apple", so under prefix rules "app" must come at or before "apple" for the list to be sorted — but "apple" appears first. This violates non-decreasing order, so the answer is NO.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →