Проверьте, является ли строка вращением другой БЕЗ конкатенации

Ответ 1

Одно простое решение состоит в их конкатенации и проверке, является ли другая подстрока конкатенированной версии.

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

Это будет работать, и на самом деле это можно сделать без какой-либо конкатенации. Просто используйте любой алгоритм поиска строк для поиска второй строки в первой, и когда вы достигнете конца, вернитесь к началу.

Например, используя Boyer-Moore, общий алгоритм будет O (n).

Ответ 2

Нет необходимости конкатенировать вообще.

Сначала проверьте длины. Если они разные, верните false.

Во-вторых, используйте индекс, который увеличивается от первого символа до последнего из источника. Проверьте, начинается ли пункт назначения со всех букв из индекса до конца и заканчивается всеми буквами перед индексом. Если в любое время это верно, верните true.

В противном случае верните false.

EDIT:

Реализация в Python:

def isrot(src, dest):
  # Make sure they have the same size
  if len(src) != len(dest):
    return False

  # Rotate through the letters in src
  for ix in range(len(src)):
    # Compare the end of src with the beginning of dest
    # and the beginning of src with the end of dest
    if dest.startswith(src[ix:]) and dest.endswith(src[:ix]):
      return True

  return False

print isrot('hello', 'lohel')
print isrot('hello', 'lohell')
print isrot('hello', 'hello')
print isrot('hello', 'lohe')

Ответ 3

Вы можете вычислить лексикографически минимальное строковое вращение каждой строки, а затем проверить, были ли они равны.

Вычисление минимального вращения равно O (n).

Это было бы хорошо, если бы у вас было много строк для тестирования, поскольку минимальное вращение можно было применить как шаг предварительной обработки, а затем вы могли бы использовать стандартную хеш-таблицу для хранения вращающихся строк.

Ответ 4

Тривиальный O (min (n, m) ^ 2) алгоритм: (n - длина S1, m - длина S2)

isRotated (S1, S2):

if (S1.length != S2.length)
    return false
for i : 0 to n-1
    res = true
    index = i
    for j : 0 to n-1
       if S1[j] != S2[index]
           res = false
           break
       index = (index+1)%n
    if res == true
        return true
return false

EDIT:

Объяснение -

Две строки S1 и S2 длин m и n соответственно являются циклически идентичными тогда и только тогда, когда m == n и существуют индекс 0 <= j <= n-1, такой S1 = S [j] S [j + 1]... S [N-1] S [0]... S [J-1].

Итак, в приведенном выше алгоритме мы проверяем, равна ли длина и существует ли такой индекс.

Ответ 5

Очень простое решение состоит в том, чтобы повернуть один из слов n раз, где n - длина слова. Для каждого из этих поворотов проверьте, совпадает ли результат с другим словом.

Ответ 6

Вы можете сделать это в O(n) время и O(1) пробел:

def is_rot(u, v):
    n, i, j = len(u), 0, 0
    if n != len(v):
        return False
    while i < n and j < n:
        k = 1
        while k <= n and u[(i + k) % n] == v[(j + k) % n]:
            k += 1
        if k > n:
            return True
        if u[(i + k) % n] > v[(j + k) % n]:
            i += k
        else:
            j += k
    return False

Подробнее см. мой ответ здесь.

Ответ 7

Простое решение в Java. Нет необходимости в итерации или конкатенации.

private static boolean isSubString(String first, String second){
        int firstIndex = second.indexOf(first.charAt(0));
        if(first.length() == second.length() && firstIndex > -1){

            if(first.equalsIgnoreCase(second))
                return true;

            int finalPos = second.length() - firstIndex ; 
            return second.charAt(0) == first.charAt(finalPos)
            && first.substring(finalPos).equals(second.subSequence(0, firstIndex));
        }
        return false;

    }

Тестовый пример:

String first = "bottle";
String second = "tlebot";

Логика:

Возьмите первый символ первой строки, найдите индекс во второй строке. Вычтите длину второго с найденным индексом, проверьте, является ли первый символ второго в 0 таким же, как символ, при разности длины второго и найденного индекса, а подстроки между этими двумя символами одинаковы.

Ответ 8

Другая реализация python (без конкатенации), хотя и не эффективна, но O (n), ожидая комментариев, если таковые имеются.

Предположим, что существуют две строки s1 и s2.

Очевидно, что если s1 и s2 являются вращениями, в s1 существует две подстроки s2, сумма которых будет равна длине строки.

Вопрос заключается в том, чтобы найти этот раздел, для которого я увеличиваю индекс в s2 всякий раз, когда char of s2 совпадает с индексом s1.

def is_rotation(s1, s2):
    if len(s1) != len(s2):
        return False
    n = len(s1)
    if n == 0: return True

    j = 0
    for i in range(n):
        if s2[j] == s1[i]:
            j += 1
    return (j > 0 and s1[:n - j] == s2[j:] and s1[n - j:] == s2[:j])

Второе и условие - просто убедиться, что счетчик, увеличенный для s2, соответствует подстроке.

Ответ 9

input1 = "hello" input2 = "llohe" input3 = "lohel" (input3 - особый случай)

если длина ввода 1 и input2 не совпадают с возвратом 0. Установите я и j два индекса, указывающих на вход 1 и input2 соответственно, и инициализируйте отсчет до значения input1.length. Введите флаг isRotated, для которого установлено значение false

while (count!= 0) {

Когда символ ввода 1 соответствует вводу2

• приращение я и j
• количество декрементов

Если символ donot соответствует

• if isRotated = true (это означает, что даже после вращения там несоответствие), поэтому break;
• else Reset j to 0 как несоответствие. Например:

Пожалуйста, найдите код ниже и дайте мне знать, если он не сработает для какой-либо другой комбинации, которую я, возможно, не рассматривал.

    public boolean isRotation(String input1, String input2) {
    boolean isRotated = false;
    int i = 0, j = 0, count = input1.length();

    if (input1.length() != input2.length())
        return false;

    while (count != 0) {

        if (i == input1.length() && !isRotated) {
            isRotated = true;
            i = 0;
        }

        if (input1.charAt(i) == input2.charAt(j)) {
            i++;
            j++;
            count--;
        }

        else {
            if (isRotated) {
                break;
            }
            if (i == input1.length() - 1 && !isRotated) {
                isRotated = true;
            }
            if (i < input1.length()) {
                j = 0;
                count = input1.length();

            }
            /* To handle the duplicates. This is the special case.
             * This occurs when input1 contains two duplicate elements placed side-by-side as "ll" in "hello" while 
             * they may not be side-by-side in input2 such as "lohel" but are still valid rotations. 
             Eg: "hello" "lohel"
            */
            if (input1.charAt(i) == input2.charAt(j)) {
                i--;
            }
            i++;
        }
    }
    if (count == 0)
        return true;
    return false;
}

public static void main(String[] args) {
    // TODO Auto-generated method stub
    System.out.println(new StringRotation().isRotation("harry potter",
            "terharry pot"));
    System.out.println(new StringRotation().isRotation("hello", "llohe"));
    System.out.println(new StringRotation().isRotation("hello", "lohell"));
    System.out.println(new StringRotation().isRotation("hello", "hello"));
    System.out.println(new StringRotation().isRotation("hello", "lohe"));
}

Ответ 10

Решение задачи в O (n)

void isSubstring(string& s1, string& s2)
{
    if(s1.length() != s2.length())
        cout<<"Not rotation string"<<endl;
    else
    {
        int firstI=0, secondI=0;
        int len = s1.length();

        while( firstI < len )
        {
            if(s1[firstI%len] == s2[0] && s1[(firstI+1) %len] == s2[1])
                break;

            firstI = (firstI+1)%len;
        }

        int len2 = s2.length(); 
        int i=0;
        bool isSubString = true; 
        while(i < len2)
        {
            if(s1[firstI%len] != s2[i])
            {
                isSubString = false;
                break;
            }
            i++;
        }

        if(isSubString)
            cout<<"Is Rotation String"<<endl;
        else
            cout<<"Is not a rotation string"<<endl;
    }
}

Ответ 11

    String source = "avaraavar";
    String dest =   "ravaraava";

    System.out.println();
    if(source.length()!=dest.length())
        try {
            throw (new IOException());
        } catch (Exception e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }

    int i = 0;
    int j = 0;
    int totalcount=0;
    while(true)
    {
        i=i%source.length();    
        if(source.charAt(i)==dest.charAt(j))
        {   
            System.out.println("i="+i+" , j = "+j);
            System.out.println(source.charAt(i)+"=="+dest.charAt(j));
            i++;
            j++;
            totalcount++;   
        }
        else
        {
            System.out.println("i="+i+" , j = "+j);
            System.out.println(source.charAt(i)+"!="+dest.charAt(j));
            i++;
            totalcount++;   
            j=0;
        }
        if(j==source.length())
        {
            System.out.println("Yes its a rotation");
            break;
        }
        if(totalcount >(2*source.length())-1)
        {
            System.out.println("No its a rotation");
            break;
        }
    }

Ответ 12

Это можно сделать в O (1) время и O (n) пространстве (С#). Обратите внимание, что фактический поиск выполняется в O (1) раз.

• Предварительная обработка исходной строки в n итерациях, где n - длина источника и добавление результата в качестве ключа к словарю.

• Возвращает true, если шаблон существует в словаре и false в противном случае.

Пример кода:

if (string.IsNullOrWhiteSpace(source) && string.IsNullOrWhiteSpace(rotated)) return true;

Dictionary<string, int> s = new Dictionary<string, int>();
string t = source;
StringBuilder builder = new StringBuilder();
for (int i = 0; i < source.Length; i++)
{
    string a = t[t.Length - 1] + builder.Append(t, 0, t.Length - 1).ToString();
    if (!s.ContainsKey(a)) s.Add(a, 0);
    t = a;
    builder.Clear();
}

return s.ContainsKey(rotated);