Есть две строки, как мы можем проверить, есть ли другая версия?
For Example : hello --- lohel
Одним простым решением является concatenating первая строка с самим собой и проверка того, является ли другой substring конкатенированной версии.
Есть ли другое решение?
Мне было интересно, можем ли мы использовать circular linked list, может быть? Но я не могу прийти к решению.
Одно простое решение состоит в их конкатенации и проверке, является ли другая подстрока конкатенированной версии.
Я предполагаю, что вы имеете в виду сцепление первой строки с самим собой, а затем проверьте, является ли другая подстрокой этой конкатенации.
Это будет работать, и на самом деле это можно сделать без какой-либо конкатенации. Просто используйте любой алгоритм поиска строк для поиска второй строки в первой, и когда вы достигнете конца, вернитесь к началу.
Например, используя Boyer-Moore, общий алгоритм будет O (n).
Нет необходимости конкатенировать вообще.
Сначала проверьте длины. Если они разные, верните 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')
Вы можете вычислить лексикографически минимальное строковое вращение каждой строки, а затем проверить, были ли они равны.
Вычисление минимального вращения равно O (n).
Это было бы хорошо, если бы у вас было много строк для тестирования, поскольку минимальное вращение можно было применить как шаг предварительной обработки, а затем вы могли бы использовать стандартную хеш-таблицу для хранения вращающихся строк.
Тривиальный 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].
Итак, в приведенном выше алгоритме мы проверяем, равна ли длина и существует ли такой индекс.
Очень простое решение состоит в том, чтобы повернуть один из слов n раз, где n - длина слова. Для каждого из этих поворотов проверьте, совпадает ли результат с другим словом.
Вы можете сделать это в 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
Подробнее см. мой ответ здесь.
Простое решение в 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 таким же, как символ, при разности длины второго и найденного индекса, а подстроки между этими двумя символами одинаковы.
Другая реализация 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, соответствует подстроке.
input1 = "hello" input2 = "llohe" input3 = "lohel" (input3 - особый случай)
если длина ввода 1 и input2 не совпадают с возвратом 0. Установите я и j два индекса, указывающих на вход 1 и input2 соответственно, и инициализируйте отсчет до значения input1.length. Введите флаг isRotated, для которого установлено значение false
while (count!= 0) {
Когда символ ввода 1 соответствует вводу2
Если символ donot соответствует
Пожалуйста, найдите код ниже и дайте мне знать, если он не сработает для какой-либо другой комбинации, которую я, возможно, не рассматривал.
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"));
}
Решение задачи в 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;
}
}
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;
}
}
Это можно сделать в 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);