leetcode/
subseq.rs

1//! # 392. 判断子序列
2//!
3//! 难度 简单
4//!
5//! 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
6//!
7//! 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
8//!
9//! 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
10//!
11//! ## 示例 1:
12//!
13//! ```text
14//! s = "abc", t = "ahbgdc"
15//! 返回 true.
16//! ```
17//!
18//! ## 示例 2:
19//!
20//! ```text
21//! s = "axc", t = "ahbgdc"
22//! 返回 false.
23//! ```
24//!
25//! ## 后续挑战 :
26//!
27//! 如果有大量输入的 S，称作 S1, S2, ... , Sk
28//! 其中 k >= 10 亿，你需要依次检查它们是否为 T 的子序列。
29//!
30//! 在这种情况下，你会怎样改变代码？
31//!
32//! See [leetcode](https://leetcode-cn.com/problems/is-subsequence/)
33
34pub struct Solution;
35
36impl Solution {
37    pub fn is_subsequence(s: String, t: String) -> bool {
38        // let matching = Matching::new(t);
39        // matching.is_match(s)
40        Self::simple_match(&s, &t)
41    }
42
43    /// 类似双指针
44    pub fn simple_match(s: &str, t: &str) -> bool {
45        t.chars().try_fold(s.chars().peekable(), |mut s, t| match s.peek() {
46            Some(&c) if c == t => { s.next(); Some(s) }
47            Some(_) => Some(s),
48            None => None, // short-circuiting
49        }).map_or(true, |mut s| s.next().is_none())
50    }
51}
52
53/// 后续挑战
54/// 预处理字符串
55pub struct Matching {
56    pos: Vec<[Option<usize>; 26]>,
57}
58
59impl Matching {
60
61    pub fn new(target: String) -> Self {
62        let len = target.len();
63        let t: Vec<_> = target.chars().collect();
64        let mut pos: Vec<[Option<usize>; 26]> = Vec::with_capacity(len);
65        while pos.len() < len {
66            pos.push([None; 26]);
67        }
68
69        for i in (0..len).rev() {
70            for j in 0..26usize {
71                if t[i] as usize == j + 'a' as usize {
72                    pos[i][j] = Some(i);
73                } else {
74                    pos[i][j] = if i + 1 < len {
75                        pos[i + 1][j]
76                    } else {
77                        None
78                    };
79                }
80            }
81        }
82
83        Self {
84            pos,
85        }
86    }
87
88    pub fn is_match(&self, s: String) -> bool {
89        if s.len() > self.pos.len() {
90            return false;
91        }
92        let mut x = 0;
93        for c in s.chars() {
94            let char_offset = c as usize - 'a' as usize;
95            if let Some(v) = self.pos.get(x).and_then(|v| v[char_offset]) {
96                x = v + 1;
97            } else {
98                return false;
99            }
100        }
101        true
102    }
103}
104
105#[cfg(test)]
106mod tests {
107    use super::*;
108
109    #[test]
110    fn test() {
111        let t1 = |s: &str, t: &str| Solution::is_subsequence(s.into(), t.into());
112        let t2 = |s: &str, t: &str| Matching::new(t.into()).is_match(s.into());
113
114        let s = "";
115        let t = "abc";
116        assert!(t1(s, t));
117        assert!(t2(s, t));
118
119        let s = "abc";
120        let t = "ahbgdc";
121        assert!(t1(s, t));
122        assert!(t2(s, t));
123
124        let s = "axc";
125        let t = "ahbgdc";
126        assert!(!t1(s, t));
127        assert!(!t2(s, t));
128
129        let s = "axc";
130        let t = "";
131        assert!(!t1(s, t));
132        assert!(!t2(s, t));
133
134        let s = "aaaaaa";
135        let t = "bbaaaa";
136        assert!(!t1(s, t));
137        assert!(!t2(s, t));
138
139        let s = "twn";
140        let t = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxtxxxxxxxxxxxxxxxxxxxxwxxxxxxxxxxxxxxxxxxxxxxxxxn";
141        assert!(t1(s, t));
142        assert!(t2(s, t));
143    }
144}
leetcode/subseq.rs

leetcode/
subseq.rs
