CODEWITHSUNDEEP
python
Jassy.W
Jassy.W

Reputation: 539

How to detect whether a string contain all elements in another string at the same time their occurrence are in order?

I need to detect whether the elements of the string 'Relim' are all in the string 'Berkelium', at the same time for each letter in 'Relim' occurs in in the string 'Berkelium' in order. For example, 'Relim' is in 'Berkelium' while occurrence of 'Relim' are in order in 'Berkelium'.

My primary idea is to loop over the string 'Berkelium', then check one by one that whether the character in 'Berkelium' equal to the element in string 'Relim', if so, record the index of this character 'Relim'. After for loop, check if all the elements 'Relim' occur in 'Berkelium' and also in a ascending order. Since I loop over the string 'Berkelium', then I can ensure the occurrence of the letters are in order, but the problem is that there are two 'e' in 'Berkelium', my codes do not work. Could anyone have idea about this?

    string1 = 'Relim'
    string2 = 'Berkelium'
    index = []
    for i, char1 in enumerate(string2):

        for j, char2 in enumerate(string1):

            if char1 == char2:
               index.append(j)
    if sorted(index) == index and len(index) == len(string1):
        result = True
    else:
        result = False

Upvotes: 2

Views: 63

Answers (3)

Terry Jan Reedy
Terry Jan Reedy

Reputation: 19144

As I understand the problem, you want to find each char in s1 in order in s2. So, for each char in s1, search s2 until you find the same char or run out. I presume case should not matter.

def s_in_s(s1, s2):
    s1 = s1.lower()
    s2it = iter(s2.lower())
    for c1 in s1:
        for c2 in s2it:
            if c2 == c1:
                break
        else:
            return False
    return True

print(s_in_s('Relim', 'Berkelium'))

This returns True as is, False without the .lower() call.

EDIT: add more test cases

for seek in ('', 'r', 'BM', 'relim', 'berkelium'):
    print(s_in_s(seek, 'Berkelium'))  # should all be True
print()
for seek in (' ', 'x', 'BMx', 'berkeslium'):
    print(s_in_s(seek, 'Berkelium'))  # should all be False

Upvotes: 1

RoadRunner
RoadRunner

Reputation: 26315

You could try this:

def sub_order(string1, string2):

    # get all the matches in the second string
    matches = [char for char in string2.lower() if char in string1.lower()]

    # record the found characters that match
    found = []

    # create stack of string1, to ensure which characters have been found
    stack = list(string1.lower())

    # Go through each character in the substring
    for match in matches:

        # If the stack is not empty, keep checking
        if stack:

            # if a character matches the character at the top of the stack
            if match == stack[0]:

                # append what character was found, and pop the stack
                found.append(match)
                stack.pop(0)

    # check if the string found matches string1
    if "".join(found) == string1.lower():
        return True

    return False

The method used here:

  • Get all the of the matching characters from string2 which occur in string1.
  • Go through each of the matching characters, and check them, using a stack based approach of knocking down characters that have already been found.
  • if an ordering was found that matches the ordering of string1, return, otherwise keep searching if possible.

Upvotes: 1

f5r5e5d
f5r5e5d

Reputation: 3706

tried a few edge cases, seems to work

matches 'backwards' by .pop()ing chars off the end of each string after conversion to lists

counts down the 'misses' and if you get to the end of lst1 and you didn't have enough matches in lst2...

lst1 = [*'Relim'.lower()]      # list conversion makes copies, the lists get wholly
lst2 = [*'Berkelium'.lower()]  # or partially consumed

ln_lst1, cnt  = len(lst1), len(lst2)

while lst1 and lst2:
    last1 = lst1.pop()
    while lst2 and lst2.pop() != last1:
        cnt -= 1

cnt >= ln_lst1

Out[264]: True

Upvotes: 1

Related Questions