本周主题：Sort
本题难度：Medium
做题日期：2017年4月07日
Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.
Example 1:
Input:s = "abpcplea", d = ["ale","apple","monkey","plea"]Output: "apple"
Example 2:
Input:s = "abpcplea", d = ["a","b","c"]Output: "a"
Note:
All the strings in the input will only contain lower-case letters.
The size of the dictionary won't exceed 1,000.
The length of all the strings in the input won't exceed 1,000.
做复杂题目的基本思路是将复杂的问题分解成几个独立或者相关的简单一点的问题。
本题可以分解成两个小问题：
如何给给定的字符串数组排序：按照字符串的长度和字母的顺序
如何判断一个字符串 w 是 字符串 s 的子序列
排序算法可以用系统库自带的 sort 方法， 比如 Java 的 Collection.sort ， Ruby 的 sort 方法， Python 的 sort 函数。其时间复杂度是 O(N*lgN)
思路
如果字符串的长度不相等
按照字符串长度递减排序： 比如字符串 "monkey" 应该排在字符串 "apple"的前面
如果字符串的长度相等
按照字母递增排序： 比如 "aac" 应该排在 "ale" 的前面
例子
字符串数组 ["ale","apple","monkey","plea”, “aac”] 经过排列后的结果是 ["monkey", "apple", "plea", "aac", "ale"]
图一
代码
图二
图二是 Ruby 的排序代码，可以当做伪代码读，我简单的解释一下：
sort！
sort! 的意思是排序，并且会改变调用该方法的对象的值
x <=> y
x <=> y 是升序排列的意思：x > y ， 则返回 -1 ；x = y ，则返回 0；x < y，则返回 1。
求给定两个字符串的最长公共子序列是非常经典的题目，需要用到动态规划。子序列的判定要简单很多，用双指针就行。
思路
用指针i, j 分别指向 s, w 字符串的头部(也就是 0 的位置)
如果 j == w.length 或者 i == s.length, 跳转到第 6 步
如果 s[i] = w[j]
i 递增 1， j 递增 1
返回 j == w.length ( 如果 j == w.length 说明 w 的每个字母在字符串 s 中都有出现 ， 否则说明 w 中存在没有出现在 s 中的字符串)
例子
求字符串 w = "apple" 是不是字符串 s = "abpcplea" 的子序列，运行如下
图三
代码
图四
思路跟上面的分析一样：先将字符串数组按照要求排序；循环字符串数组，每个字符串 与 模式串 s 匹配，判断其是否是 s 的子序列：如果是，则返回该字符串，如果不是则继续循环。
时间复杂度：排序算法 O(N*lgN) + 子序列判断 O(N * P) =~ O(N*lgN) ( 其中 P 是字符串 s 的长度。
空间复杂度：O(1)
图五：代码由 @郭方舟 提交
这个思路先不排序，而是用一个变量 cur 保存当前的最佳值，当字符串 w 是 s 的子序列，并且其长度大于 cur 或者 其字母排序 小于 cur, 则替换 cur 为当前的字符串。
由于其不需要排序，所以需要遍历 d 中的所有字符串，并且每次循环都需要做三个判断：子序列，长度比较 和 字母排序比较。
每日一道算法题是一个纯粹的算法学习社区：通过每天一起做一道算法题来提升我们的算法能力。
长按下面的二维码，关注每日一道算法题公众号，跟我们一起学习算法！
群规
《每日一题算法群》群规
[每日一题]项目宣言：一起来重复造轮子吧
代码规范
[每日一题]代码规范v1.0
排序问题
[每日一题]179. Largest Number
