facebook

原题链接：https://leetcode.com/problems/decode-ways/#/description 题目： A message containing letters from  A-Z  is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing digits, determine the total number of ways to decode it. For example, Given encoded message  "12" , it could be decoded as  "AB"  (1 2) or  "L"  (12). The number of ways decoding  "12"  is 2. 解题思路：这道题主要是要想到用dynamic programming来保存前一位和前两位的decode方法数。另外一些corner case比如以0开头的或者超过26的需要考虑。 代码： public int numDecodings(String s) { if (s == null || s.length() == 0 ){ return 0 ; } int [] dp = new int [s.length() + 1 ]; dp[ 0 ] = 1 ; dp[ 1 ] = valid(s.substring( 0 , 1 )) ? 1 : 0 ; for ( int i = 2 ; i <= s.length() ; i++){ if (valid(s.substring(i - 1 , i))){ dp[i] = dp[i - 1 ]; } if (valid(s.substring(i - 2 , i))){ ...

题目地址：https://leetcode.com/problems/word-break/#/description 题目： Given a  non-empty  string  s  and a dictionary  wordDict  containing a list of  non-empty  words, determine if  s  can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words. For example, given s  =  "leetcode" , dict  =  ["leet", "code"] . Return true because  "leetcode"  can be segmented as  "leet code" . 思路： 这道题看似可以直接用twopointer来解决，但是对于s = aaaaaaa， word是aaa和aaaa是会有问题的。所以这题只能够用dynamic programming来解决。但是中间会用到twopointer的思想。 代码： public boolean wordBreak(String s, List<String> wordDict) { if (s == null || s.length() == 0 ){ return false ; } boolean [] valid = new boolean [s.length() + 1 ]; valid[ 0 ] = true ; for ( int fast = 1 ; fast <= s.length(); fast++){ for ( int slow = 0 ; slow <= fast - ...