Определить, является ли предложение палиндромом

Question

Задали решить такую задачу: Вводится предложение (последний символ - '\0'). Нужно определить, является ли оно палиндромом (палиндром - когда последовательность символов читается одинаково в ту и другую сторону, например - шалаш). При этом, пробелы учитываться не должны (например: "ш а лаш" - тоже палиндром). Все бы ничего, да по ходу выполнения задачи добавились новые условия, которые не были указаны, а именно:

нельзя изменять входную строку (т.е. удалять из нее пробелы и т.п.);
нельзя создавать доп. массивы;
Нельзя делить строку на 2 половины.

Честно говоря, не знаю, каким образом это реализовать...

Вот код, когда я пробовал делить строку на 2 массива:

int is_palin(char *str, int len, int kol_s){
  char str1[len],str2[len];
  int i,k,symbols;
  symbols=i=0;

  while(1){
    if(symbols>kol_s)break;
    str1[i]=str[i];
    if(str[i]!=' ') symbols++;
    i++;
  }
  str1[i]='\0';
  symbols=0;
  i=len;
  while(1){
    if(symbols>kol_s)break;
    str1[len-i]=str[i];
    if(str[i]!=' ') symbols++;
    i--;
  }
  str2[i]='\0';
  k=0;

  for(i=0;str1[i]!='\0';i++){
    while(str2[k]==' ') k++;
    while(str1[i]==' ') continue;
    if(str2[k]!=str1[i]){return 0;}
  }


    return 1;
}

Как понимаете, это мне не зачли из-за очередных "нововведений" в условие. Подскажите, пожалуйста, каким образом можно реализовать эту функцию, чтобы она соответствовала новому условию?

Answer 1

Вот так не годится? (защиты "от дурака" не написаны)

int is_pndrm(const char * s)
{
    int ok = 1;
    for(const char * b = s, * e = s + strlen(s) - 1; b < e; b++, e--)
    {
        while(*b == ' ') ++b;
        if (b > e) break;
        while(*e == ' ') --e;
        if (*b != *e) { ok = 0; break; }
    }
    return ok;
}

Answer 2

Берете два указателя. Один ставите на начало строки, второй в конец и начинаете проверять, что под этими указателями одинаковые символы. Если да, то сдвигаем оба указателя к центру. Если под указателем оказывается пробел, то смещаем этот указатель. Алгоритм повторять, пока левый указатель не достигнет правого

Answer 3

Псевдокод на языке типа C# с двумя указателями

bool IsPoly(string input)
{
    int left = 0;
    int right = input.Length - 1;

    while (left < right)
    {
        while (input[left] == ' ' && left < right) left++;
        while (input[right] == ' ' && right > left) right--;        
        if (input[left++] != input[right--]) return false;      
    }

    return true;
}

Answer 4

Этот вариант алгоритмически мало отличается от других. Как мне кажется для него легче убедится что решение корректное - условие b < e проверяется на каждой итерации и у указателей нет шанса выйти за пределы строки.

#include <assert.h>
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>

bool is_palindrom(const char *s) {
    assert(s != NULL);

    const size_t len = strlen(s);
    if (len == 0) {
        return true;
    }
    const char *b = s;
    const char *e = s + len - 1;
    while (b < e) {
        if (isspace(*b)) {
            ++b;
            continue;
        }
        if (isspace(*e)) {
            --e;
            continue;
        }
        if (*b == *e) {
            ++b;
            --e;
            continue;
        }
        return false;
    }
    return true;
}

int main(int argc, char **argv) {
    for (int i = 1; i < argc; ++i) {
        const char *s = argv[i];
        printf("[%s] %s\n", s, (is_palindrom(s) ? "YES" : "NO"));
    }
}

$ gcc -std=c17 -pedantic -Wall -Wextra -Werror -O3 is-palindrom.c

$ ./a.out "" a aa aba abba ab "a b ba" "a  b   ba" "  a  b   ba " "         "
[] YES
[a] YES
[aa] YES
[aba] YES
[abba] YES
[ab] NO
[a b ba] YES
[a  b   ba] YES
[  a  b   ba ] YES
[         ] YES

БЛОГ НА HUSL

Определить, является ли предложение палиндромом

Ответы (4 шт):