Борьба с поиском ближайшего вхождения символа в строке

Question

Я пытаюсь найти закрывающее повторение вхождения символа в строке, но я застрял и не знаю, как поступить.

Вопрос похож на пример:

String s= "babab" с индексом, заданным как 2, найти ближайшее вхождение этого символа.поэтому 0 и 4 здесь, где 0 ближе всего к 2.

То, что у меня есть,

public static List<Integer> closest(String s, List<Integer> queries) {
    // Write your code here
        int min;
        int count = 0;
        List<Integer> ans = new List<Integer>();
        for(int i=0; i<queries.size(); i++){
            char a = s.charAt(i);
            for(int j=0; j<s.length(); j++){
                if(s[j] == a ){
                    int count = j;
                }else{
                    count = -1;
                }
            }
        }
    }

Answer 1

Если я понял проблему, вы можете сделать это за O (n) раз.

Algo: input (String s, int idx)

1. Создать списоккоторый хранит все индексы вхождений этого конкретного символа, кроме самого idx.

2. Initialize min_difference = Integer.MAX_VALUE и closestIndex = -1.

3. Итерируйте по списку и рассчитайте разницу модов индекса в списке с idx, сохраняя min_difference и closestIndex.

Например,для строки "babab" и idx = 2 затем:

После выполнения первого шага созданный нами список имеет вид {0, 4}

На шаге 3 мы выполняем | 2 - 0 |= 2 (обновить min_difference = 2, closestIndex = 0) и | 2 - 4 |= 2 (на данный момент от вашего требования зависит, хотите ли вы какой-либо closestIndex. Это ваш выбор - обновлять или нет).

Answer 2

Строковое API-решение

Строковый API на самом деле может помочь вам сделать все это намного проще.

Вы можете использовать indexOf (int, int) , чтобы найтиследующее использование чарса.Вы можете использовать substring (int, int) , чтобы просматривать только часть строки.И вы можете использовать lastIndexOf (int) , чтобы найти самое последнее вхождение символа.

Используя эти методы, ваш метод поиска для каждой строки будет выглядеть примерно так

public static int closest(String s, int index) {
    char target = s.charAt(index);
    int next = s.indexOf(target, index+1);
    int previous = s.substring(0, index).lastIndexOf(target);
    //The below code probably needs so work to handle not found case (ie -1)
    if (index-previous <= next-index) {
        return previous;
    } else {
        return next;
    }
}

Затем вы можете использовать это в своей предыдущей функции:

public static List<Integer> closest(String s, List<Integer> queries) {
    queries.stream().mapToInt(I -> closets(s,i)).collect(Collectors.toList());
}

Answer 3

Я не уверен, правильно ли я понял проблему, но здесь есть потенциальное решение.Обратите внимание, что эта программа имеет сложность O (n * m), где m = количество запросов и n = длина строки.Это может быть дополнительно оптимизировано.

import java.util.ArrayList;
import java.util.List;

public class Main {

public static List<Integer> closest(String s, List<Integer> queries) {
    List<Integer> result = new ArrayList<Integer>();
    //execute each query separately
    for(int i=0; i<queries.size(); i++){
        char target = s.charAt(queries.get(i));
        int index = queries.get(i);
        int length = s.length();

        int currentStep = 1;
        boolean founded = false;
        //search for the closest character
        while(index-currentStep>=0 || index+currentStep<length){
            if(index-currentStep>=0 && s.charAt(index-currentStep)==target){
                result.add(index-currentStep);
                founded = true;
                break;
            }else if(index+currentStep<length && s.charAt(index+currentStep)==target){
                result.add(index+currentStep);
                founded = true;
                break;
            }
            currentStep++;
        }
        if(!founded){
            //we couldn't find the element
            result.add(-1);
        }
    }
    return result;
}

public static void main(String[] args) {
    String s = "babab";
    List<Integer> queries = new ArrayList<Integer>();
    queries.add(2);

    List<Integer> result = closest(s,queries);
    for(Integer res: result){
        System.out.println(res);
    }
}

}

Обновление: Вот решение со сложностью O (max (n, m)).Позвольте мне немного проанализировать сложность.Во-первых, эта проблема не может быть решена менее чем за O (n), поскольку мы должны получить доступ к каждому символу хотя бы один разКроме того, для каждого запроса у нас есть как минимум один доступ с любым алгоритмом, поэтому он требует как минимум m шагов (если мы запустим алгоритм параллельно с m рабочими, сложность будет O (n)).Теперь решение: мы создаем пару структур данных, которые нам помогут (в prepareDb).Этот процесс занимает 3 * n, его можно немного оптимизировать, но это все равно дает O (n).Затем мы просто запрашиваем массив, который содержит индекс ближайшего элемента, который делает m шагов для m запросов (O (m)).Наконец, это дает O (n) + O (m) или O (max (n, m)) в сумме.Вот решение:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Main {

public static List<Integer> prepareDb(String s) {
    List<Integer> result = new ArrayList<>();

    //fron similar
    HashMap<Integer, Integer> dbFront = new HashMap<>();
    HashMap<Character, Integer> lastSeenFront= new HashMap<>();
    for(int i = 0; i<s.length();i++){
        Character c = s.charAt(i);
        int distance = -1;
        if(lastSeenFront.containsKey(c)){
            distance = i - lastSeenFront.get(c);
        }
        lastSeenFront.put(c,i);
        dbFront.put(i, distance);
    }

    //backSimilar
    HashMap<Integer, Integer> dbBack = new HashMap<>();
    HashMap<Character, Integer> lastSeenBack = new HashMap<>();
    for(int i = s.length()-1; i >= 0;i--){
        Character c = s.charAt(i);
        int distance = -1;
        if(lastSeenBack.containsKey(c)){
            distance = lastSeenBack.get(c) - i;
        }
        lastSeenBack.put(c,i);
        dbBack.put(i, distance);
    }

    for(int i = 0; i<s.length();i++){
        //distance between i and the closest element
        int distance = dbFront.get(i);
        if(dbFront.get(i)==-1 || (dbBack.get(i)!=-1 && dbFront.get(i)>dbBack.get(i))){
            distance = dbBack.get(i);
        }
        result.add(distance);
    }
    return result;
}


public static List<Integer> closest(String s, List<Integer> queries) {
    List<Integer> result = new ArrayList<Integer>();

    List<Integer> db = prepareDb(s);

    //execute each query separately
    for(int i=0; i<queries.size(); i++){
        result.add(db.get(queries.get(i)));
    }
    return result;
}

public static void main(String[] args) {
    String s = "babab";
    List<Integer> queries = new ArrayList<Integer>();
    queries.add(2);

    List<Integer> result = closest(s,queries);
    for(Integer res: result){
        System.out.println(res);
    }
}

}