Блог

Итак, вот чего я пытаюсь достичь. Я пытаюсь создать код, который выполняет следующее из 2 заданных строк: a target и a source .

 //  Determines whether the string TARGET occurs as a substring of string SOURCE where "gaps" are allowed between characters of target.`
//  That is, the characters in TARGET occur in SOURCE in their given order but do not have to be adjacent.`
//  (Pictured another way, this method returns true if TARGET could be obtained from SOURCE by removing some of the letters of SOURCE.)`
//  This method is case sensitive. For example,`
//  containsWithGaps("hamburgers", "mug") returns true`
//  containsWithGaps("hamburgers", "burrs") returns true`
//  containsWithGaps("hamburgers", "hamburgers") returns true`
//  containsWithGaps("hamburgers", "gum") returns false`
//  containsWithGaps("hamburgers", "hamm") returns false`
//  containsWithGaps("hamburgers", "") returns true`
//  Parameters:`
//  SOURCE - the given string in which to find the target characters`
//  TARGET - the characters to be found`

//  Returns:`
//  true if the characters in TARGET can be found as a subsequence in SOURCE, false otherwise`
  

И вот код, который я написал. Это кажется слишком сложным для того, что, по моему мнению, не должно быть сложной задачей, но, несмотря ни на что, я все равно продолжаю получать ошибки, и это не будет работать, если задана ИСХОДНАЯ строка hamburgers с ЦЕЛЕВОЙ строкой burr :

     public static boolean substringWithGaps(String source, String target) {

    boolean substring = false;
    int[] target_index;
    target_index = new int [target.length()];

    if (target.length() > source.length()) {
        substring = false;
    }
    else {
        for (int i = 0; i < target.length(); i  ) {
            if (source.contains(""   target.charAt(i))) {           
                target_index[i] = target.indexOf(i);
                i  ;
            }
            else {
                target_index[i] = target.indexOf(i);
                i  ;
            }
        }
        for (int i = 0; i < target_index.length; i  ) {
            if (target_index[i] == -1) {
                substring = false;
                break;
            }
            else if (target_index[i] >= target_index[i 1]) {
                substring = false;
                break;
            }
            else {
                substring = true;
            }
        if (target_index.length != target.length()) {
            substring = false;
            }
        }   
    }
    return substring;
}
  

Есть идеи?

Должно быть довольно просто:

 public static boolean substringWithGaps(String source, String target) {
    int targetIndex = 0;
    for (int i = 0; i < source.length(); i  ) {
        if (source.charAt(i) == target.charAt(targetIndex)) {
            targetIndex = targetIndex   1;
            if (targetIndex == target.length()) {
                return true;
            }
        }
    }
    return false;
}
  

Мы сохраняем указатель следующей буквы , которую нам нужно найти внутри target . Затем мы перебираем source поиск по этой букве, и когда мы находим ее, мы перемещаем индекс в пределах target прямой единицы. Если индекс target когда-либо равен длине target , это означает, что мы нашли все нужные нам символы. Если мы перебираем весь исходный код, не находя всех target , мы возвращаем false .

Это должно быть сделано следующим образом.

 public static boolean containsWithGaps(String a, String b){
    if(b.length() > a.length())
    {
      return false;
    }
    char[] targetChars = new char[b.length()];
    b.getChars(0,b.length(),targetChars, 0);
    int pos = 0;
    for(char myChar : targetChars)
    {
      pos = a.indexOf(myChar, pos);
      if(pos == -1)
      {
        return false;
      }
    }
    return true;
  }
  

Небольшая оптимизация в том смысле, что она возвращается, как только символ не может быть сопоставлен (и не завершается сбоем, если цель имеет нулевую длину)

 public static boolean substringWithGaps(String source, String target) {
    for (int i = 0, last = -1; i < target.length(); i  ) {
        if (-1 == (last = source.indexOf(target.charAt(i), last   1)))
            return false;
    }
    return true;
}