Udało mi się wymyślić stosunkowo prosty algorytm, który działa w czasie O(n^2) (zakładając O(1) iterowanie po stringu):
Kopiuj
use std::collections::{HashMap, HashSet};
#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
struct Change {
from: char,
to: char,
}
impl Change {
fn new(from: char, to: char) -> Self {
Self { from, to }
}
}
fn transform(from: &str, to: &str) -> Result<Vec<Change>, ()> {
assert_eq!(from.len(), to.len());
// Spis transformacji `z jakiego znaku => na jaki znak`
// (nie możemy tutaj wykorzystać hash-setu albo btree-setu, gdyż istotna
// jest kolejność operacji)
let mut changes = Vec::new();
// Zbiór zużytych transformacji
// (wykorzystujemy go do de-duplikacji zwróconego wektora tak, abyśmy nie
// zwracali niepotrzebnie wielokrotnie tych samych transformacji)
let mut performed_changes = HashSet::new();
// Zbiór wykorzystanych znaków wyjściowych
// (wykorzystywany do szybkiego wyszukiwania proxy-znaków)
let mut used_chars: HashSet<_> = to.chars().collect();
// Mapa `z jakiego znaku => na jaki znak`
// (wykorzystujemy ją do wykrywania sytuacji w której transformacja nie jest
// wzajemnie jednoznaczną)
let mut used_mappings = HashMap::new();
let mut pending_changes = Vec::new();
for (pos, (from_ch, to_ch)) in from.chars().zip(to.chars()).enumerate() {
if from_ch == to_ch {
continue;
}
if let Some(to_ch2) = used_mappings.insert(from_ch, to_ch) {
// To porównanie umożliwia nam wykrycie sytuacji, w której
// transformacja nie jest wzajemnie jednoznaczna dla danych
// argumentów (np. `aa` -> `bc`)
if to_ch != to_ch2 {
return Err(());
}
}
// Aby określić czy wymagany jest proxy znak (np. dla `ab` -> `ba`),
// sprawdzamy czy *w przyszłości* (w następnych znakach) planujemy
// wykorzystać zamianę `* -> to_ch`.
//
// Dodatkowy warunek `from_ch2 != to_ch2` umożliwia nam zgrabne ogranie
// sytuacji w stylu `bbnndd` -> `dddddd`, do których bez tego warunku
// również zostałby zastosowany (niepotrzebnie) proxy-znak
let requires_proxy = from
.chars()
.zip(to.chars())
.skip(pos)
.find(|(from_ch2, to_ch2)| {
from_ch2 != to_ch2
&& *from_ch2 == to_ch
})
.is_some();
if requires_proxy {
let proxy_ch = ('a'..='z')
.filter(|char| !used_chars.contains(char))
.next()
.ok_or(())?;
used_chars.insert(proxy_ch);
changes.push(Change::new(from_ch, proxy_ch));
pending_changes.push(Change::new(proxy_ch, to_ch));
} else {
let change = Change::new(from_ch, to_ch);
if performed_changes.insert(change) {
changes.push(change);
}
}
}
changes.extend(pending_changes);
Ok(changes)
}
fn main() {
println!("{:?}", transform("ggg", "hhh"));
println!("{:?}", transform("bbnndd", "dddddd"));
println!("{:?}", transform("xx", "ga"));
println!("{:?}", transform("ah", "ha"));
}
(https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=2a042c78808fe7c891d41b47b2d920a7)
Wydaje mi się, że można by spróbować zamienić pętlę z let requires_proxy = /* ... */; na hashmapę znak => liczba pozostałych transformacji, dzięki czemu całość zamykałaby się w O(n).
Plus, dla optymalizacji pamięci, zdaje się, że można by się również pozbyć performed_changes na rzecz used_mappings.
