Найти строку соответствия позиции?

Question

У меня есть такая строка: PQqRrp. Письмо в верхнем регистре, за которым следует строчная буква.

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

Теперь мне нужно найти последнюю позицию, в которой совпадал мой персонаж (верхний с его нижним алфавитом). В приведенном выше случае на 5-м месте, r was matching with R.

private int getStringMatchNumber(String input) { 
    char[] str = input.toLowerCase().toCharArray(); 
    // now I am confuse 
} 

Как сюда перейти?

Answer 1

Вы можете начать с конца строки и идти в обратном направлении, в псевдокоде:

char[] str = input.toCharArray() 
for i = str.length-1 down to 1: 
    if str[i] is lowercase: 
     if toLowerCase(str[i-1]) == str[i] and str[i-1] is uppercase: 
     return i-1 

return -1 // means no match is found 

Java код:

char[] str = input.toCharArray(); 

    for(int i=str.length-1; i>=1; --i) { 
     char c = str[i]; 
     char p = str[i-1]; 
     if (c == Character.toLowerCase(c) && p == Character.toUpperCase(p)){ 
      if (Character.toLowerCase(p) == c) 
       return i-1; 
     } 
    } 
    return -1; 

Answer 2

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

Я бы запускал цикл for из конца массива символов и проверял каждую последовательную пару значений, если они равны или нет. Поскольку цикл выполняется с конца, первый экземпляр совпадения возвращает значение i. Обратный подход эффективен, так как вы ищете последний матч. Метод также использует только один if-conditional, поэтому в конечном итоге объем памяти будет меньше.

private static int getStringMatchNumber(String input) { 
    char[] str = input.toCharArray(); 
    for(int i = str.length-1; i > 0; i--) { 
     Character c = str[i]; 
     Character p = str[i-1]; 
     if (Character.isLowerCase(c) && Character.isUpperCase(p)){ 
      if (p == Character.toUpperCase(c)) 
       return i; 
     } 
    } 
    return 0; 
} 

Обратите внимание, что если функция возвращает 0, это означает, что не найдено совпадающих пар. Вы можете проверить это после вызова.

EDIT Я внедрил проверку для строчных и прописных букв в соответствующих элементах (как это было предложено другими). Имейте в виду, что возвращаемое значение - это значение zero-based позиции символа с нижним очерком в матче. Для входного значения "aaaBbaa" возвращается значение 4, то есть позиция b в матче Bb. Вы можете настроить алгоритм, чтобы вернуть позицию B, вернув i-1 вместо i. В этом случае вам нужно будет вернуть -1 вместо 0, чтобы избежать ложных негативов.

Answer 3

Другие ответы (в том числе принятого один) не учитывают (например, A a в ABba), которые должны возвращать 3, но другие решения возвращают 2, так как они не могут соответствовать A с a)

Предлагаемое грубое решение:

private static int getStringMatchNumber(String input) { 
    char[] str = input.toCharArray(); 

    int last = findMatches(str, 0); 
    System.out.println("Last unmatched index: " + (last - 1)); 

    for(int i = str.length-1; i > 0; i--) { 
     Character c = str[i]; 
     Character p = str[i-1]; 
     if (Character.isLowerCase(c) && Character.isUpperCase(p)){ 
      if (p == Character.toUpperCase(c)) 
       return i; 
     } 
    } 
    return 0; 
} 

private static int findMatches(char[] str, int pos) { 

    if(pos+1 >= str.length) { 
     return pos; 
    } 
    Character c = str[pos]; 
    Character p = str[pos+1]; 
    int nextPos = 0; 

    System.out.println(c + " " + p); 

    if (Character.isUpperCase(c) && Character.isLowerCase(p)){ 
     if (c == Character.toUpperCase(p)) { 
      System.out.println("Match found"); 
      pos = pos+2; 
      pos = findMatches(str, pos); 
     } else { 
      System.out.println("Next lower case letter doesn't match. Stop."); 
     } 
    } else if(Character.isUpperCase(c) && Character.isUpperCase(p)) { 
     System.out.println("Trying to find inner Matches first"); 

     nextPos = findMatches(str, pos+1); 
     if(nextPos < str.length) { 
      p = str[nextPos]; 
      System.out.println("Outer match character: " + p); 
      System.out.println(c + " " + p); 

      if ((Character.isUpperCase(c) && Character.isLowerCase(p)) && (c == Character.toUpperCase(p))){ 
       System.out.println("Outer Match found"); 
       pos = nextPos + 1; 
      } else { 
       pos = nextPos; 
      } 
     } 
     if(pos < str.length) { 
      pos = findMatches(str, pos); 
     } 
    } else { 
     System.out.println("Lower case letter found, will return and find outer match"); 
    } 

    return pos; 
}