How to implement python out-of-order string sorting

Python out-of-order string sort

What is out-of-order string sorting

Out-order string sorting refers to the out-order sorting of one string that is another string. For example, apple is the out-order string of Eppal.

examine

Suppose the string consists of 26 lowercase strings.

1. Time complexity O(n^2)

Solution:

Determine whether the lengths of the two strings are equal. If they are not equal, return False. If they are not equal, judge whether the characters of the first string are in the second string. If they are not, return False. If they are not, set the position element found in the second string to None. Because to change the second string, the second string needs to be converted to list. The code is as follows:

def none_sort_str(s1, s2):
    s2_list = list(s2)
    if len(s1) != len(s2):
        return False
    else:
        for i in range(len(s1)):
            for j in range(len(s2_list)):
                if s1[i] in s2_list:
                    s2_list[s2_list.index(s1[i])] = None
                    break
                else:
                    return False
    return True

2. Time complexity O(n)

Solution:

To determine whether the lengths of the two strings are equal. If they are not equal, return False, use the counting method, the code is as follows:

def none_sort_str2(s1, s2):
    a = [0] * 26
    b = [0] * 26
    for i in range(len(s1)):
        index1 = ord(s1[i]) - ord('a')
        a[index1] += 1
    for i in range(len(s2)):
        index2 = ord(s2[i]) - ord('a')
        b[index2] += 1
    if a == b:
        return True
    else:
        return False

Research on the algorithm for checking out-of-order strings

A good example of an algorithm showing different orders of magnitude is out-of-order checking of strings. Out-order strings are the rearrangement of one string just another string.

For example, 'heart' and 'earth' are out-of-order strings. So are 'python' and 'typhon'. For simplicity, we assume that the two strings in question have equal lengths and that they are composed of a collection of 26 lowercase letters. Our goal is to write a boolean function that takes two strings as arguments and returns whether they are out of order.

Solution 1

Idea: convert both strings into a list, then iterate through one of them, and remove the corresponding element of the other list in the other list (prevent repeated interference). If it does not exist, it will return FALSE, and if it is completed, it will return True.

The code reference is as follows:

str1 = 'hagjen'
str2 = 'ahejng'
def foo(str1,str2):
    ls1 = list(str1)
    ls2 = list(str2)
    for i in ls1:
        if i in ls2:
            (i)
        else:return False
    return True
print(foo(str1,str2))

Algorithm complexity: Both layers of for loops are linearly correlated with n, so the complexity of this algorithm is O(n^2).

Solution 2

Both strings are also converted into lists, and then sorting is done. When the lists are equal, it returns True, otherwise FALSE

str1 = 'hagjen'
str2 = 'ahejng'
def foo(str1,str2):
    ls1 = list(str1).sort()
    ls2 = list(str2) .sort()
    return True if ls1==ls2 else False
print(foo(str1,str2))

Algorithm complexity: At first glance, there is no loop at all, and the complexity seems to be very low, but don’t forget to sort it! Sort is implemented internally in Python, and it also requires time consumption. The complexity of sorting algorithms is generally O(nlog(n)) and O(n^2). So this method is not necessarily better than the above

Solution Three

Create two lists of length 26, traverse two strings, count them separately, and return True if the last two lists are the same

def foo(s1,s2):
    ls1 = list(s1)
    ls2 = list(s2)
    count1 = [0 for  i in range(26)]
    count2 = [0 for  i in range(26)]
    print(count1)
    print(count2)
    for  i in ls1:
        count1[ord(i)-ord('a')] +=1
    for  i in ls2:
        count2[ord(i)-ord('a')] +=1
    return True if count1==count2 else False
print(foo('aacf','cfaa'))

Time complexity: Since there is no loop nesting or sorting algorithm, the time complexity is 2n+26, that is, O(n)

Code optimization:

def is_simlar(s1, s2):
    from collections import Counter
    return Counter(s1) == Counter(s2)

The above is personal experience. I hope you can give you a reference and I hope you can support me more.