题解 | #小美的子序列#

题意

多行字符串中，每行只取一个字母，问是否能构成字符串中包含 “meituan”。例如，“mmmmmeemeituaaattn” 包含 “meituan”，而 “emituan” 并不包含 “meituan”。

思路

暴力遍历即可，当找到一个字符后，继续找下一个目标字符，不用考虑顺序问题。

import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;

import static java.util.Arrays.deepToString;


public class Main {

    static boolean LOCAL = Boolean.parseBoolean(System.getenv("LOCAL"));
    static boolean TO_FILE = Boolean.parseBoolean(System.getenv("LOCAL"));
    static Scanner sc = new Scanner(System.in);
    static void debug(Object... os) {
        System.err.println(deepToString(os));
    }

    public static void main(String[] args) {

        if (LOCAL) {
            try {
                System.setIn(new FileInputStream("./data/in.txt"));
            } catch (Throwable e) {
                LOCAL = false;
            }
        }

        if (TO_FILE) {
            try {
                System.setOut(new PrintStream("./data/output.txt"));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }

    static class Task {
        Random random = new Random(751454315315L + System.currentTimeMillis());
        static final int MAXN = (int)1e6 + 10;
        static final long INF = (long)1e18;
        static final double EPS = 1e-7;
        static final double PI = Math.acos(-1.0);
        static final long MOD = (long)1e9 + 7;

        public void solve(InputReader in, PrintWriter out) {
            int t = 1;
//            t = in.nextInt();
            while (t-- > 0) {
                solveSingle(in, out);
            }
        }

        public void solveSingle(InputReader in, PrintWriter out) {
            int n = in.nextInt(), m = in.nextInt();
            char[][] c = new char[n][m];
            
            String str = "meituan";
            int cur = 0;
            
            for (int i = 0; i < n; i++) {
                c[i] = in.nextLine().toCharArray();
            }
            
            
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (cur < str.length() && c[i][j] == str.charAt(cur)) {
                        cur++;
                        break;
                    }
                }
            }
            
            
            out.println(cur == str.length() ? "YES" : "NO");
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public float nextFloat() {
            return Float.parseFloat(next());
        }

        public BigDecimal nextBigDecimal() { return new BigDecimal(next()); }

        public String nextLine(){
            while (tokenizer == null || !tokenizer.hasMoreElements()){
                try{
                    tokenizer = new StringTokenizer(reader.readLine());
                }catch (IOException e){
                    e.printStackTrace();
                }
            }
            return tokenizer.nextToken("\n");
        }

    }
}

复杂度分析

时间复杂度： $O(nm)$ ，其中 $n$ 是字符串的个数， $m$ 是字符串的长度。
空间复杂度： $O(nm)$ ，定义了二维数组来存储所有字符串，其实可以优化成 O(m)，因为每个字符串只用遍历检查一次。