Submission #61255442

---

Source Code Expand

#![allow(dead_code)]

use proconio::{input, marker::Chars};

trait Bound<T> {
    fn lower_bound(&self, x: &T) -> usize;
    fn upper_bound(&self, x: &T) -> usize;
}

impl<T: PartialOrd> Bound<T> for [T] {
    fn lower_bound(&self, x: &T) -> usize {
        let (mut low, mut high) = (0, self.len());
        while low + 1 < high {
            let mid = (low + high) / 2;
            if self[mid] < *x {
                low = mid;
            } else {
                high = mid;
            }
        }
        if self[low] < *x {
            low + 1
        } else {
            low
        }
    }

    fn upper_bound(&self, x: &T) -> usize {
        let (mut low, mut high) = (0, self.len());
        while low + 1 < high {
            let mid = (low + high) / 2;
            if self[mid] <= *x {
                low = mid;
            } else {
                high = mid;
            }
        }
        if self[low] <= *x {
            low + 1
        } else {
            low
        }
    }
}

fn levenshtein_distance(word1: &str, word2: &str) -> usize {
    let w1 = word1.chars().collect::<Vec<_>>();
    let w2 = word2.chars().collect::<Vec<_>>();

    let word1_length = w1.len() + 1;
    let word2_length = w2.len() + 1;

    let mut matrix = vec![vec![0; word1_length]; word2_length];

    for i in 1..word1_length {
        matrix[0][i] = i;
    }
    for j in 1..word2_length {
        matrix[j][0] = j;
    }

    for j in 1..word2_length {
        for i in 1..word1_length {
            let x: usize = if w1[i - 1] == w2[j - 1] {
                matrix[j - 1][i - 1]
            } else {
                1 + std::cmp::min(
                    std::cmp::min(matrix[j][i - 1], matrix[j - 1][i]),
                    matrix[j - 1][i - 1],
                )
            };
            matrix[j][i] = x;
        }
    }
    matrix[word2_length - 1][word1_length - 1]
}

fn main() {
    input! {k:usize,s:Chars,t:Chars}
    if s.len() == t.len() {
        let mut diffs = 0;
        for (si, ti) in s.iter().zip(t.iter()) {
            if si != ti {
                diffs += 1;
            }
        }

        if diffs <= k {
            println!("Yes");
        } else {
            println!("No")
        }
    } else {
        let mut sidx = 0;
        let mut tidx = 0;
        let s_is_longer = s.len() > t.len();

        let mut diffs = 0;
        while s.len() > sidx && t.len() > tidx {
            if s[sidx] != t[tidx] {
                diffs += 1;
                if s_is_longer {
                    sidx += 1;
                } else {
                    tidx += 1
                }
            } else {
                sidx += 1;
                tidx += 1;
            }
        }

        let slen = s.len();
        let tlen = t.len();
        if sidx != slen || tidx != tlen {
            diffs += (slen - sidx).max(tlen - tidx);
        }

        if diffs <= k {
            println!("Yes")
        } else {
            println!("No")
        }
    }
}

Submission Info

Judge Result