Python | Check the order of characters in a string using OrderedDict ()


  Input:  string = "engineers rock" pattern = "er";  Output:  true  Explanation:  All `e` in the input string are before all` r`.  Input:  string = "engineers rock" pattern = "egr";  Output:  false  Explanation:  There are two `e` after` g` in the input string.  Input:  string = "engineers rock" pattern = "gsr";  Output:  false  Explanation:  There are one `r` before` s` in the input string. 

We have a solution to this problem, see OrderedDict () . The approach is very simple,

  • Create an OrderedDict of the input string that contains the characters of the input strings as the only key .
  • Now set the pointer at the beginning of the template string .
  • Now loop through the generated OrderedDict and match the keys to a single character of the template string, if the key and character match, then increment the pointer by 1.
  • If the template pointer reaches its end , this means that the line follows the order of the characters defined by the pattern, otherwise not.

# Function to check if a line is in order
# of characters defined by the template

from collections import OrderedDict


def checkOrder ( input , pattern):


# create empty OrderedDict

# the output will look like {& # 39; a & # 39 ;: no, & # 39; b & # 39 ;: no, & # 39; c & # 39 ;: no}

dict = OrderedDict.fromkeys ( input )


# traverse generated OrderedDict in parallel with

# string template to check if character order is

# same or not

  ptrlen = 0  

for key, value in dict . iteritems ():

  if (key = = pattern [ptrlen]):

ptrlen = ptrlen + 1


# check if we have a full move

# sample line

if (ptrlen = = ( len (pattern))):

return `true`


  # if we break out of the for loop it means

# order does not match

return `false`

# Driver program

if __ name__ = = "__ main__" :

input = `engineers rock`  

pattern = `egr`

  print checkOrder ( input , pattern)



This article is courtesy of Shashank Mishra (Gullu) . If you are as Python.Engineering and would like to contribute, you can also write an article using or by posting an article contribute @ See my article appearing on the Python.Engineering homepage and help other geeks.

Please post comments if you find anything wrong or if you`d like to share more information on the topic discussed above.