Выяснение того, могут ли строки быть анаграммами
У меня есть строка s1 и строка s2. Я хочу проверить, можно ли сделать s1 анаграммой s2, удалив один символ ноль или более раз из s1 и удалив один символ ноль или более раз из s2.
Примеры
Пример 1:
s1 = "safddadfs"
s2 = "famafmss"
Result = true
Объяснение:
s1имеет 2 х «а», 2 х «д», 2 х «ж», 2 х «с»s2имеет 2 х «а», 2 х «м», 2 х «ж», 2 х «с»
Мы можем удалить «d» из s1 и удалить «m» из s2, чтобы сделать их анаграммами: и s1, и s2 станут 2 x «a», 2 x «f», 2 x «s».
Пример 2:
s1 = "aaabb"
s2 = "aabbb"
Result = true
Объяснение:
s1имеет 3 х «а», 2 х «б»s2имеет 2 х «а», 3 х «б»
Мы можем удалить одну «а» из s1 и одну «b» из s2, чтобы сделать их анаграммами: оба станут 2 x «a», 2 x «b».
Пример 3:
s1 = "aab"
s2 = "ab"
Result = true
Объяснение:
s1имеет 2 х «а», 1 х «б»s2имеет 1 х «а», 1 х «б»
Мы можем удалить одну букву «а» из s1 и ничего из s2, чтобы сделать их анаграммами: оба станут 1 x «a», 1 x «b».
Пытаться
Я попытался реализовать код для этого следующим образом:
import java.util.*;
public class Main {
public static boolean solve(String s1, String s2) {
Map<Character, Integer> m1 = getCountMap(s1);
Map<Character, Integer> m2 = getCountMap(s2);
boolean valid = canBeAnagrams(m1, m2);
if (!valid) {
valid = canBeAnagrams(m2, m1);
}
return valid;
}
private static boolean canBeAnagrams(Map<Character, Integer> m3, Map<Character, Integer> m4) {
int count = 0;
Map<Character, Integer> m1 = new HashMap<>(m3), m2 = new HashMap<>(m4);
for(char c : m1.keySet()) {
int v1 = m1.get(c);
int v2 = m2.getOrDefault(c,0);
if (v1 != v2) {
count++;
}
m2.remove(c);
if (count > 1) return false;
}
if (m2.size() > 1) return false;
return true;
}
private static Map<Character, Integer> getCountMap(String s) {
Map<Character, Integer> countMap = new HashMap<>();
for (char c : s.toCharArray()) {
countMap.put(c, countMap.getOrDefault(c, 0) + 1);
}
return countMap;
}
public static void main(String[] args) {
System.out.println(solve("safddadfs", "famafmss")); // Should print true
System.out.println(solve("aaabb", "aabbb")); // Should print true, but getting false
System.out.println(solve("aab", "ab")); // Should print true
}
}
Проблема
Мой код не работает в тестовом примере, где s1 = "aaabb" и s2 = "aabb".
Где у меня ошибка в логике и как это исправить?
@trincot removing a single character (any number of times) from each string s1 and s2 итак s1 = a:3, b:2 и s2 = a:2,b:3 , поэтому я удалю одиночный a из s1 и одиночный b из s2, чтобы сделать их анаграммой
Хорошо, значит, вам не нужно удалять из них все вхождения. Я понимаю.
@JerryCoffin, это была опечатка, сейчас исправлю
Ответы 2
Есть две проблемы:
Когда
v1 != v2есть только одна из строк, из которой необходимо удалить соответствующий символ (один или несколько раз), чтобы сделать обе строки равными по отношению к этому символу, но, поскольку вы потенциально вызываетеcanBeAnagramsдважды, вы затем засчитаете это изменение дважды, один раз. для каждой строки. Это сравнение должно бытьv1 > v2, чтобы исправить это.Код вызова имеет
if (!valid)в качестве условия для совершения второго звонка. Но это означает, что если первый вызов вернетfalse, все равно есть вероятность, что конечный результат будетtrue. Это неправильно. Если один звонок вернетfalse, то всё. С другой стороны, когда вы получаетеtrueот первого звонка, вы все равно можете получитьfalseот противоположной проверки, поэтому затем следует сделать второй звонок. Короче говоря, этоifдолжно бытьif (valid).
После устранения этих двух проблем все должно работать.
Улучшения
Однако вы можете сделать это с меньшим количеством обходов и без вызовов remove. Рассмотрим разницу в количестве на одну букву. Вы бы позволили одному отличию быть отрицательным, а другому - положительным, не более того. Таким образом, вы можете изменить карту, созданную для второй строки, вычитая счетчики, собранные в первой карте, а затем посмотреть, верно ли это условие:
public static boolean solve(String s1, String s2) {
Map<Character, Integer> m1 = getCountMap(s1);
Map<Character, Integer> diff = getCountMap(s2);
boolean occurred[] = { false, false };
for (char c : m1.keySet()) {
diff.put(c, diff.getOrDefault(c, 0) - m1.get(c));
}
for (char c : diff.keySet()) {
int delta = diff.get(c);
if (delta == 0) continue;
int side = delta > 0 ? 1 : 0;
if (occurred[side]) return false;
occurred[side] = true;
}
return true;
}
Улучшенный код выглядит красиво. :-)
Я бы сделал это немного по-другому. Я бы посчитал символы в первой строке примерно так же, как вы сейчас, но для второй строки я бы посчитал вниз (на той же карте).
Когда вы закончите, вы сможете создать анаграмму, если у вас есть не более двух ненулевых значений, только одно из которых может быть положительным, а другое — отрицательным.
На C++ (извините, я не особо разбираюсь в Java) это будет выглядеть примерно так:
#include <string>
#include <map>
#include <iostream>
#include <tuple>
#include <cassert>
#include <vector>
bool solve(std::string const &s1, std::string const &s2) {
std::map<char, int> counts;
for (auto const c : s1)
++counts[c];
for (auto const &c : s2)
--counts[c];
int pos = 0;
int neg = 0;
for (auto [_, count] : counts) {
if (count > 0) ++pos;
else if (count < 0) ++neg;
}
return pos <= 1 && neg <= 1;
}
int main() {
using TestType = std::tuple<std::string, std::string, bool>;
using std::get;
std::vector<TestType> tests {
{ "safddadfs", "famafmss", true},
{ "aaabb", "aabbb", true},
{ "aab", "ab", true},
{ "abc", "abcde", false},
};
for (auto const &test : tests) {
assert(solve(get<0>(test), get<1>(test)) == get<2>(test));
}
}
Один из способов облегчить жизнь и стандартный способ набора анаграмм — это перед началом работы отсортировать буквы двух слов в алфавитном порядке. Тогда гораздо легче увидеть и запрограммировать логику для поиска различий.