регулярное выражение для поиска частей строки в другой - PullRequest
3 голосов
/ 19 декабря 2008

У меня есть две строки: первое значение "catdog", а второе "got".

Я пытаюсь найти регулярное выражение, которое сообщает мне, находятся ли буквы "got" в "catdog". Я особенно стараюсь избегать случаев, когда есть дубликаты букв. Например, я знаю, что «got» - это совпадение, однако «gott» - это не совпадение, потому что в «catdog» нет двух «t».

EDIT:

Основываясь на ответе Адама ниже, это код C #, который я получил, чтобы работать в своем решении. Спасибо всем, кто откликнулся.

Примечание: мне пришлось преобразовать char в int и вычесть 97, чтобы получить соответствующий индекс для массива. В моем случае буквы всегда строчные.

    private bool CompareParts(string a, string b)
    {

        int[] count1 = new int[26];
        int[] count2 = new int[26];

        foreach (var item in a.ToCharArray())
            count1[(int)item - 97]++;

        foreach (var item in b.ToCharArray())
            count2[(int)item - 97]++;

        for (int i = 0; i < count1.Length; i++)
            if(count2[i] > count1[i])
                return false;

        return true;
    }

Ответы [ 7 ]

7 голосов
/ 19 декабря 2008

Вы используете не тот инструмент для работы. Это не то, что регулярные выражения способны легко обрабатывать. К счастью, это сделать довольно легко без регулярных выражений. Вы просто подсчитываете количество вхождений каждой буквы в обеих строках и сравниваете счетчики между двумя строками - если для каждой буквы алфавита счетчик в первой строке не меньше, чем счетчик во второй строке тогда ваши критерии удовлетворены. Поскольку вы не указали язык, вот ответ в псевдокоде, который должен быть легко переведен на ваш язык:

bool containsParts(string1, string2)
{
    count1 = array of 26 0's
    count2 = array of 26 0's

    // Note: be sure to check for an ignore non-alphabetic characters,
    // and do case conversion if you want to do it case-insensitively
    for each character c in string1:
        count1[c]++
    for each character c in string2:
        count2[c]++

    for each character c in 'a'...'z':
        if count1[c] < count2[c]:
            return false

    return true
}
3 голосов
/ 19 декабря 2008

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

Рассмотрим следующий код, который выполняет это в одной строке кода:

MatchString.ToList().ForEach(Item => Input.Remove(Item));

Что можно использовать следующим образом:

public bool IsSubSetOf(string InputString, string MatchString) 
{
  var InputChars = InputString.ToList(); 
  MatchString.ToList().ForEach(Item => InputChars.Remove(Item)); 
  return InputChars.Count == 0;
}

Затем вы можете просто вызвать этот метод, чтобы проверить, является ли он подмножеством или нет.

Здесь интересно то, что «got» вернет список без элементов, потому что каждый элемент в строке совпадения появляется только один раз, а «gott» вернет список с одним элементом, потому что будет только один вызов убрать «т» из списка. Следовательно, вы бы оставили пункт в списке. Таким образом, «gott» не является подмножеством «catdog», а «gott» есть.

Вы можете сделать еще один шаг вперед и поместить метод в статический класс:

using System;
using System.Linq;
using System.Runtime.CompilerServices;

static class extensions
{
    public static bool IsSubSetOf(this string InputString, string MatchString)
    {
        var InputChars = InputString.ToList();
        MatchString.ToList().ForEach(Item => InputChars.Remove(Item));
        return InputChars.Count == 0;
    }
}

, который превращает ваш метод в расширение строкового объекта, что в конечном итоге значительно облегчает работу, так как теперь вы можете делать свои вызовы следующим образом:

Console.WriteLine("gott".IsSubSetOf("catdog"));
0 голосов
/ 20 декабря 2008

Лучший способ сделать это с помощью регулярных выражений, IMO:

A. Сортировка символов в большую строку (пространство поиска) Таким образом: превратить «catdog» в «acdgot»

B.

  1. Сделайте то же самое со строкой, в которой вы будете искать символы:

  2. Вставьте «.*» между каждым из этих символов

  3. Используйте последнее как регулярное выражение для поиска в первом.

Например, какой-нибудь Perl-код (если не возражаете):

$main = "catdog"; $search = "gott";
# break into individual characters, sort, and reconcatenate
$main = join '', sort split //, $main;
$regexp = join ".*", sort split //, $search;
print "Debug info: search in '$main' for /$regexp/ \n";
if($main =~ /$regexp/) {
    print "Found a match!\n";
} else {
    print "Sorry, no match...\n";
}

Это печатает:

Debug info: search in 'acdgot' for /g.*o.*t.*t/
Sorry, no match...

Бросьте одну букву "t", и вы получите совпадение.

0 голосов
/ 19 декабря 2008

@ Решение Адама Розенфилда на Python:

from collections import defaultdict

def count(iterable):
    c = defaultdict(int)
    for hashable in iterable:
        c[hashable] += 1
    return c

def can_spell(word, astring):
    """Whether `word` can be spelled using `astring`'s characters."""

    count_string = count(astring)
    count_word   = count(word)

    return all(count_string[c] >= count_word[c] for c in word)
0 голосов
/ 19 декабря 2008

Чарли Мартин почти правильно понял, но вы должны сделать полный проход для каждого письма. Вы можете сделать это с помощью одного регулярного выражения, используя lookaheads для всех, кроме последнего прохода:

/^
 (?=[^got]*g[^got]*$)
 (?=[^got]*o[^got]*$)
 [^got]*t[^got]*
$/x

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

0 голосов
/ 19 декабря 2008

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

/^(c?a?t?d?o?g?|c?a?t?d?g?o?| ... )$/

Теперь, с небольшой хитростью, вы можете сделать это с помощью нескольких регулярных выражений (например, в Perl, не тестировано):

$foo = 'got';
$foo =~ s/c//;
$foo =~ s/a//;
...
$foo =~ s/d//;
# if $foo is now empty, it passes the test.

Разумные люди будут использовать цикл, конечно:

$foo = 'got'
foreach $l (split(//, 'catdog') {
    $foo =~ s/$l//;
}
# if $foo is now empty, it passes the test.

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

0 голосов
/ 19 декабря 2008

Вы хотите строку, которая точно соответствует этим буквам, ровно один раз. Это зависит от того, в чем вы пишете регулярное выражение, но это будет что-то вроде

^[^got]*(g|o|t)[^got]$

Если у вас есть оператор для «ровно одного совпадения», это поможет.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...