Эффективный способ сравнения двух строк (порядок символов не имеет значения)

Question

Я пытаюсь придумать алгоритм для сравнения двух строк. Было бы зарегистрировать совпадение любых слов, которые содержат одинаковые буквы. Например, рента и крачка будут эквивалентны, потому что они оба содержат буквы r, e, n, t.

РЕДАКТИРОВАТЬ Я прошу прощения за столь расплывчато. Сравнение будет сделано по двум наборам из нескольких тысяч слов сотни раз. Это лишь малая часть всего кода, поэтому я не хочу, чтобы он все мешал.

Для тех, кто спрашивал «да», было бы очень важно, чтобы совпадение имело место, например, рента также соответствовала бы тройне.

РЕДАКТИРОВАТЬ 2 Для совпадения типа арендной платы == ternicate, ternicate не будет соответствовать арендной плате. Это больше похоже на то, что слово два содержит буквы слова один. Поэтому, если у вас есть дополнительные буквы, это все равно будет совпадение, если слово содержит все буквы первого слова.

Answer 1

Я думаю, вы должны построить дерево. Я написал немного кода на Python, чтобы проиллюстрировать эту идею, но, вероятно, он содержит ошибки:

class knot():
    def __init__(self, char, is_word, string = "" way = 0):
        self.children = []
        self.shortest_way = way
        self.char = char
        self.word = is_word
        self.string = string

def comparing(strings):
    sorted_strings = []
    for string in strings:
        array_of_string = []
        for char in string:
            array_of_string.append(char)
        sorted_strings.append(array_of_string.sort())
    sorted_strings.sort()

    start = []
    matches = []

    for array_of_string in sorted_strings:
        matches += insert_string(array_of_string, start)

def insert_string(array, start):
    for match_string in test_string(array, start):
        matches += (array, match_string.string)
    add_string(array, start, 0):

def add_string(array, knots, n):
    minimum = 0
    maximum = len(knots) - 1
    while minimum != maximum:
        num = int((minimum + maximum) / 2)
        if (knots[num].char > array[n]):
            minimum = num
        elif (knots[num].char < array[n]):
            maximum = num
        elif (knots[num].char == array[n]):
            return add_string(array, knots[num], n+1)
    knots.append(new_knots(array, n))
    knots.sort

    """ more insertion routine needed"""

def search_children(array, knots):
    minimum = 0
    maximum = len(knots) - 1
    while minimum != maximum:
        num = int((minimum + maximum) / 2)
        if (knots[num].char > array[0]):
            minimum = num
        elif (knots[num].char < array[0]):
            maximum = num
        elif (knots[num].char == array[0]):
            return test_string(array, knots[num])
    return []

def test_string(array, target_knot):
    if len(array) > target_knot.sortest_way + 1:
        return []
    match_knots = []
    if len(array) == 1 and target_knot.is_word == True:
        match_knots.append(target_knot)
    for i in range(1, len(array)):
        match_knots += search_children(array[i:], target_knot.children)
    return match_knots

Answer 2

Это довольно расплывчато, но я бы использовал ассоциативный массив для его решения:

Используйте каждую букву каждого слова в качестве ключа к ассоциативному массиву целых чисел. Буквы одного слова увеличивают значения, а другие уменьшают. Затем, в конце, вы можете запустить foreach через все ключи и проверить, что все значения равны нулю, а затем он совпадает. Это дает вам базовую арендную плату == Tren функциональность.

Предостережения за неопределенность: 1. Если с несколькими буквами все в порядке, например, rent == rreenntt, то при добавлении букв в массив проверьте, существует ли ключ, и если он существует, не добавляйте его снова. 2. Если с дополнительными буквами все в порядке, например, rent == renter, но fernt! = Renter, то при проверке значений массива в конце убедитесь, что 1 и -1 не входят в массив одновременно Другими словами, только 1 и 0 в порядке, или -1 и 0 в порядке, но не 1 и -1 не могут быть в массиве одновременно.

Я не знаю, насколько быстро это будет относительно других подходов, но это было бы легко реализовать.