AtCoder Beginner Contest 454 D

https://atcoder.jp/contests/abc454/tasks/abc454_d

リスト構造を作って、パターンにマッチすれば削除します。

// (xx)
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn YesNo(b: bool) -> String {
    return if b { "Yes" } else { "No" }.to_string()
}


//////////////////// List ////////////////////

struct Item {
    value: char,
    prev: usize,
    next: usize
}

impl Item {
    fn new(value: char, prev: usize, next: usize) -> Item {
        Item { value, prev, next }
    }
}

struct List {
    first: usize,
    data: Vec<Item>,
}

impl List {
    // removeしたItemの前のindexを返す
    fn remove(&mut self, p: usize) -> usize {
        if p == self.first {
            // このときだけ後のindexを返す
            self.first = self.data[p].next;
            self.data[self.first].prev = usize::MAX;
            self.first
        }
        else {
            let prev = self.data[p].prev;
            let next = self.data[p].next;
            self.data[prev].next = next;
            if next != usize::MAX {
                self.data[next].prev = prev
            }
            prev
        }
    }
    
    fn to_string(&self) -> String {
        let mut cs: Vec<char> = vec![];
        let mut p: usize = self.first;
        while p != usize::MAX {
            cs.push(self.data[p].value);
            p = self.data[p].next
        }
        cs.into_iter().collect::<String>()
    }
    
    fn create(s: String) -> List {
        let N = s.len();
        let values: Vec<char> = s.chars().collect();
        let prevs: Vec<usize> = (0..N).map(|i| if i == 0 { usize::MAX }
                                                    else { i - 1 }).collect();
        let nexts: Vec<usize> = (0..N).map(|i| if i == N-1 { usize::MAX }
                                                    else { i + 1 }).collect();
        let data: Vec<Item> = (0..N).map(|i| Item::new(values[i],
                                                        prevs[i], nexts[i])).
                                                                    collect();
        List { first: 0, data }
    }
}


//////////////////// process ////////////////////

fn is_matched(mut p: usize, list: &List) -> bool {
    let cs: Vec<char> = vec!['(', 'x', 'x', ')'];
    for i in (0..4).rev() {
        if p == usize::MAX || list.data[p].value != cs[i] {
            return false
        }
        p = list.data[p].prev
    }
    true
}

fn remove_each(mut p: usize, list: &mut List) -> usize {
    p = list.remove(p);
    p = list.data[p].prev;
    p = list.data[p].prev;
    list.remove(p)
}

fn remove(s: String) -> String {
    let mut list = List::create(s);
    let mut p: usize = 0;
    while p != usize::MAX {
        if is_matched(p, &list) {
            p = remove_each(p, &mut list)
        }
        else {
            p = list.data[p].next
        }
    }
    list.to_string()
}

fn F_each(A: String, B: String) -> bool {
    remove(A) == remove(B)
}

fn F(T: usize) {
    for _ in 0..T {
        let A: String = read();
        let B: String = read();
        println!("{}", YesNo(F_each(A, B)))
    }
}

fn main() {
    let T: usize = read();
    F(T)
}