[数据结构与算法]序列自动机

序列自动机

日常刷leetcode学习算法

题目来源

leetcode 524. 通过删除字母匹配到字典里最长单词

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回?dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。

示例 1：

输入：s = “abpcplea”, dictionary = [“ale”,“apple”,“monkey”,“plea”]
输出：“apple”

题目分析

该题主要涉及到两个子问题

1. 字典中某个字符串是字符串s的子序列

2. 满足条件一的长度最长且字典序最小的字符串

这个题目不算难，最初的想法就是先把字典中所有的字符串按长度从小到大排序，长度相同的字符串按字典序从大到小排序，这个数据预处理可以利用jdk的自带的排序和比较算法很快写出；而判断子序列时双指针是个再经典不过的解法

题解（未优化）

public class Solution {

    public String findLongestWord(String s, List<String> dictionary) {

        //按长度优先，其次字典序对字典中字符串进行排序
        dictionary.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if(o1.length()==o2.length()) //长度相同
                {
                    return o2.compareTo(o1);
                }
                else return o1.length()-o2.length();
            }
        });
        for(int i=dictionary.size()-1;i>=0;i--)
        {
            String s1 = dictionary.get(i);
            if(isSubString(s,s1))return s1;
        }
        return "";
    }
    //判断某个字符串的子序列
    public boolean isSubString(String s,String str)
    {
        int i=0;
        int j=0;
        while(i<s.length()&&j<str.length())
        {
            if(s.charAt(i)==str.charAt(j))
            {
                i++;
                j++;
            }
            else{
                i++;
            }
        }
        if(j==str.length())return true;
        return false;
    }
}

这里处理第一个子问题（字符串的子序列）用到的算法时间复杂度为O(m*n), m?表示?s?的长度，n?表示dictionary?中字符串的平均长度。

可以用序列自动机算法，用于子序列匹配。对第一个子问题的算法进行优化

本质上还是动态规划的思想,我们可以使用动态规划的方法实现预处理，令 f[i][j] 表示字符串 s 中从位置 i 开始往后字符 j第一次出现的位置。在进行状态转移时，如果 s 位置 i的字符就是 j，那么 f[i][j]=i，否则 j出现在位置 i+1开始往后，即 f[i][j]=f[i+1][j]；因此我们要倒过来进行动态规划，从后往前枚举 i。

优化后的算法

public class DP {

    public String findLongestWord(String s, List<String> dictionary) {

        //按长度优先，其次字典序对字典中字符串进行排序
        dictionary.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if(o1.length()==o2.length()) //长度相同
                {
                    return o2.compareTo(o1);
                }
                else return o1.length()-o2.length();
            }
        });
        //创建dp数组并根据状态转移方程，往其中添值
        int m=s.length();
        int [][]dp=new int[m+1][26];
        //用于边界值处理
        for(int i=0;i<26;i++)
            dp[m][i]=-1;
        for(int i=m-1;i>=0;i--)
        {
            for(int j=0;j<26;j++)
            {
                if(s.charAt(i)==('a'+j))dp[i][j]=i;
                else dp[i][j]=dp[i+1][j];
            }
        }

        for(int i=dictionary.size()-1;i>=0;i--)
        {
            String s1 = dictionary.get(i);
            int k=0;
            int l;
            for(l=0;l<s1.length();l++)
            {
                int i1 = dp[k][s1.charAt(l) - 'a'];
                if(i1==-1)break;
                k=i1+1;
            }
            if(l>=s1.length())return s1;
        }
        return "";
    }
}