CODEWITHSUNDEEP
stringalgorithm
YaSh Chaudhary
YaSh Chaudhary

Reputation: 2725

How to find and check if any sub-string and its reverse exist in given string?

Example

suppose string given is 'abccbaad'

Then, sub-string will be 'abc' and its reverse will be 'cba'

both exist in the given string.

how will you find both of them ?

please provide code snippets if possible.

Note: length of substring > 1

update: characters used in a substring from a position should not be used again in reversed string.

For eg. suppose 'c' from index 2 is used in substring then, it again should not be used in reversed string but 'c' from index 3 is allowed.

Upvotes: 1

Views: 1636

Answers (1)

Ganesh Tata
Ganesh Tata

Reputation: 1195

I am assuming that you want to find all substrings whose reverse is also present in the given string.

In that case, building on top of this answer - find all substrings : 

def get_all_substrings(input_string):
    output_strings = list()
    length = len(input_string)
    for i in xrange(length): # Iterate through all indices of the string
        for j in xrange(i + 1, length):  # Iterate through indices starting from i + 1 to end of the string, so as to obtain substrings of length > 1
            substr = input_string[i:j + 1] # Slice the substring
            if substr[::-1] in input_string: # Check if the substring's reverse exists in the original string
                output_strings.append(substr) # If it does, add it to a list
    return output_strings
print get_all_substrings("abccbaad") # Output - ['ab', 'abc', 'abcc', 'abccb', 'abccba', 'bc', 'bcc', 'bccb', 'bccba', 'cc', 'ccb', 'ccba', 'cb', 'cba', 'ba', 'aa']

Upvotes: 1

Related Questions