Найти время, затраченное на строку S2

Question

Представьте, что у вас есть специальная клавиатура со всеми клавишами в одном ряду.Раскладка символов на клавиатуре обозначается строкой S1 длиной 26. Индекс S1 индексируется от 0 до 25. Первоначально индекс равен 0. Для ввода символа нам нужно переместить индекс нужного символа.Время, необходимое для перемещения индекса с i на j, равно | ji |где ||является абсолютным значением

Для строки s1 и s2 опишите время, необходимое для ввода строки s2.

Для двух строк S1 и S2, где S1 = abcdeghijklmnopqrstuvwxyz

s2 = cba

и, начиная с индекса 0 ('A'), найдите время, необходимое для ввода cba.

index of c = 2
count = 2 - 0
count = 2 + 1 (c to b )
count = 2 + 1(c to b) + 1 (b to a)
count returned should be 4.

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

Answer 1

Большой Редактировать

На самом деле, по определению, тот факт, что S1 является фиксированной длиной и не зависит от ввода S2, означает, что ответ @ Amiy правильный. Поскольку indexOf работает только на S1, потребуется максимум 26 постоянных шагов. O(26n) = O(n). Мой ответ - только нижняя константа, которая варьируется от 1n до 2n в зависимости от вариации.

---

Другое Править

Для общего случая, когда S1 также является переменным вводом, и мы не можем делать никаких предположений по этому поводу, см. Решение хэширования @ user000001 в O(nlogm).

---

Оригинальные ответы

Если вы полагаетесь на тот факт, что S1 отсортирован, и что каждый символ является значением 1 от его соседей, вы можете просто вычислить разницу между символами в S2 и суммировать ее

Например:
S2 = cba

Добавьте a к S2, чтобы получить начальное значение:
S2 = acba

Для каждого символа c1 и его правого соседа c2 в S2,
distance += |c1 - c2|

---

Если вы не полагаетесь на тот факт, что S1 отсортирован (что, вероятно, то, что вы ищете), вы можете проиндексировать значения S1 в массив и применить алгоритм, аналогичный описанному выше:

Например:

S1 = "qwertyuiopasdfghjklzxcvbnm"
arr = array of size 26
let i = 0
for each character c in S1:
    arr[c - 'a'] = i++

Затем адаптируйте алгоритм:

S2 = "cba"
let distance = 0
for each character c1 and its right-neighbour c2 in S2:
    distance += |arr[c1 - 'a'] - arr[c2 - 'a']|

---

Оба алгоритма решают проблему в O(n), тогда как первый использует O(1) пробел, а второй использует O(n) пробел.

Answer 2

Это проще для понимания:

String s1 = "abcdefghijklmnopqrstuvwxyz";
String s2 = "cba";
int jumps = 0;

for(int i=0; i<s2.length();i++){

        if(i==0){
            jumps += s1.indexOf(s2.charAt(i));
        }else{
            jumps += Math.abs(s1.indexOf(s2.charAt(i)) - s1.indexOf(s2.charAt(i-1)));
        }
}
System.out.println("Total Jumps: "+jumps);

Здесь он ищет каждый символ s2 в s1 с циклом. Сначала будет запущен блок if, а затем else для оставшихся символов. Для каждого символа в s2 он продолжит добавлять количество прыжков / прыжков / времени, взятых к итогу, и вернет вас после завершения цикла.

Кроме того, он подсчитывает скачки, вычитая позицию символа того места, где мы находимся, из позиции символа того места, где мы были. Проще говоря, поскольку он начинается с позиции 0, вы можете рассчитывать так: [(C-0)+(B-C)+(B-A)].

Answer 3

Вот алгоритм на Java:

String s1 = "abcdefghijklmnopqrstuvwxyz";
String s2 = "cba";

int pos = 0;
int time = 0;

for (int ind = 0;ind < s2.length(); ind++) {
    char cur_char = s2.charAt(ind);
    index = s1.indexOf(cur_char);
    time += Math.abs(index - pos);
    pos = index;
}

System.out.println("Time taken: " + time);

Для вышеприведенных значений вывод: Time taken: 4

Edit:
Временная сложность этого алгоритма составляет O (n)
Поскольку длина s1 постоянна, пусть k.
И длина строки s2 переменная, пусть n.
Временная сложность: O (nk) = O (n) [Так как k является постоянным значением]

Answer 4

Один из способов уменьшить сложность с O (N ^ 2) до O (Nlog (N)) - создать HashMap из строки.

Примерно так:

String s1 = "abcdeghijklmnopqrstuvwxyz";
String s2 = "cba";

Map<Byte, Integer> map = new HashMap<>();

int i = 0;
for (Byte b: s1.getBytes()) {
    map.put(b, i++);
}

int result = 0;
int previndex = 0;
for (Byte b: s2.getBytes()) {
    int currentindex = map.get(b);
    result += (int) Math.abs(currentindex - previndex);
    previndex = currentindex;
}

System.out.println("resutlt= " + result);