Отсортировать буквы внутри слова

21 Август 2019 - Время чтения: 16 минуты

Задача: Дана строка из слов, разделённых пробелами. В каждом слове отсортировать буквы внутри слова, исключая первую и последнюю. Например, из строки "hello world" должно получиться "hello wlord".

Решение: Для языков, поддерживающих регулярные выражения, решение тривиально. Мы составляем соответствующее выражение, и заменяем все удовлетворяющие ему подстроки на ту же строку, только отсортированную.


Исходный код на C#
using System;
using System.Linq;
using System.Text.RegularExpressions;
 
class Program
{
    private static Regex re = new Regex(@"(?<=\b\w)\w\w+(?=\w\b)");
 
    public static void Main()
    {
        for (string s; !String.IsNullOrEmpty(s = Console.ReadLine());)
        {
            Console.WriteLine(re.Replace(s, m => new String(m.Value.OrderBy(x => x).ToArray())));
        }
    }
}

Читается регулярное выражение (?<=\b\w)\w\w+(?=\w\b) следующим образом: мы ищем все последовательности из "буква и ещё как минимум одна буква" (т.е. минимум две буквы, ведь одну букву сортировать бессмысленно), которой предшествует последовательность "граница слова и буква", а после неё идёт последовательность "буква и граница слова". Граница слова - это любая не-буква, например пробел, начало или конец строки. Строго говоря, \w означает не только букву, но и знак подчёркивания, но в данной задаче это неважно.

Регулярное выражение написано на скорую руку. Если эту статью читают знатоки регэкспов, возможно они предложат другой, более изящный и/или эффективный вариант. Я старался написать как можно проще.


Исходный код на Python
import re
 
while True:
    s = input()
    if not s:
        break
    print(re.sub(r"(?<=\w)\w\w+(?=\w)", lambda m: "".join(sorted(m.group())), s))

Практически аналогичный код, регулярные выражения везде почти одинаковы, хотя нюансы есть в каждом языке программирования. Кстати, можете заметить, что пока я писал вариант этого кода на Python, немного улучшил регулярку. Действительно, зачем нам проверять границы слов? Регулярное выражение срабатывает на первом вхождении, и пытается найти самую длинную подстроку. Поэтому в любом случае будут найдены нужные слова, и только они.

Но что если у нас нет регулярных выражений? Например, потому что мы программируем на C или Pascal?

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

Исходный код на C99
#include <ctype.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
 
#define MAX_LEN 255
 
char buf[MAX_LEN + 1];
 
int charcmp(const void *a, const void *b)
{
    return *(char *)a - *(char *)b;
}
 
int main(void)
{
    while (fgets(buf, MAX_LEN + 1, stdin) && *buf != '\n') {
        size_t len = 0;
        char *i;
        for (i = buf;; ++i) {
            if (*i == '\0' || isspace(*i)) {
                if (len > 3u) {
                    qsort(i - len + 1u, len - 2u, sizeof(char), charcmp);
                }
                len = 0;
            } else {
                ++len;
            }
            if (*i == '\0' || *i == '\n') break;
        }
        *i = '\0';
        printf("%s\n", buf);
    }
    return 0;
}

До савдииня! :)

Currently there are no comments, so be the first!

Коротко обо мне

Меня зовут Вадим Тукаев, я репетитор по информатике и программированию. Вы можете сконтактировать со мной по почте vadimtukaev@gmail.com или по скайпу pol6energetik. Рассмотрю и другие предложения о сотрудничестве, включая, но не ограничиваясь, написание заказного ПО для Windows/Linux.

Категории