本周主题：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 的长度。
