DP-2dimention

97. Interleaving String

Given a list of unique words. Find all pairs of distinct indices(i, j)
in the given list, so that the concatenation of the two words, i.e.words[i] + words[j]
is a palindrome.
Example 1:Givenwords
=["bat", "tab", "cat"]
Return[[0, 1], [1, 0]]
The palindromes are["battab", "tabbat"]

Example 2:Givenwords
=["abcd", "dcba", "lls", "s", "sssll"]
Return[[0, 1], [1, 0], [3, 2], [2, 4]]
The palindromes are["dcbaabcd", "abcddcba", "slls", "llssssll"]

---

思考

• 理解题意
  这道题目的特点是要在两个字符串s1、s2里面轮流找slice,交织拼接成s3
  注意的地方是sclice必须是连续的，比如下面的情况就不合理：
  s1 : sliceA, sliceB, sliceC
  s2 : sliceD, sliceE
  s3 = A D C E B, 因为这里虽然满足了 s1 s2的slice是轮流出现的，
  但是对于s1 来说，slice出现的次序是 ： ACB， 不是顺序的ABC，所以不满足“交织”这个概念
  正确的一个列子是：s3 = A D B E C

思路

• 怎么满足“交替出现”---> 2 个方向
• 找得到的时候怎么样？找不到的时候怎么样？
  （1）回溯 ?（back until true, and restart again）
  （2）DP ?（go froward because you know you are the outcome of your previous ones）

策略

1. 回溯的思路【较为直观，实现繁琐，辅助变量较多】

• 两个指针，代表在s1, s2中移动到下一个待匹配字符的位置
• 因为是轮流出现，所以需要一个 count 用奇偶来表示whose turn
• 找不到的话需要退回去，所以需要一个path来记录前面的拼接方式
• 加入“贪心”的小策略，在s1或者s2中单独找的时候，是一直找到最长的那个匹配字符，如果不行，需要回退的时候，长度-1，如果长度已经是1了，就需要在path中弹出。这个过程需要更新count

2. dp的思路【相对抽象，更加简洁，快】

• “两个方向” --> matrix 的两个维度
• 要在s1,s2中轮流找 -->

if(  (str1[i-1]==str3[i+j-1] && map[i-1][j]==true)   ||
      (str2[j-1]==str3[i+j-1] && map[i][j-1]==true)   )
        map[i][j] = true;
// 正因为是交替出现，所以str1和str3匹配的时候，
// 要看前一个str2是不是和str3匹配。反之亦然。

• 如何“记忆化”搜索？
• 怎么提高速度？
  • 剪枝？
  • 2 列代替整个矩阵
  • 编程语言上的优化技巧
• 要注意的地方
  dp[len1+1][len2+1], 索引str1和str2的时候要记得-1

---

实现

具体代码

    public boolean isInterleave(String s1, String s2, String s3) {
        if(s1==null || s2==null || s3==null)
            return false;
        if(s1.length() + s2.length() != s3.length())
            return false;
        
        int len1 = s1.length();
        int len2 = s2.length();
        boolean[][] map = new boolean[len1+1][len2+1];
        
        map[0][0] = true;
        
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        char[] str3 = s3.toCharArray();
        
        for(int i=1; i<len1+1; i++)
        {
            if(str1[i-1]==str3[i-1] && map[i-1][0]==true )
                map[i][0] = true;
            else
                break;
        }
        
        for(int j=1; j<len2+1; j++)
        {
            if(str2[j-1]==str3[j-1] && map[0][j-1]==true)
                map[0][j] = true;
            else
                break;
        }
        
        for(int i=1; i<len1+1; i++)
        {
            for(int j=1; j<len2+1; j++)
            {
                if( (str1[i-1]==str3[i+j-1] && map[i-1][j]==true) ||
                    (str2[j-1]==str3[i+j-1] && map[i][j-1]==true) )
                    map[i][j] = true;
            }
        }
        return map[len1][len2];
    }

---

优化

• 怎么提高速度？
  • 剪枝？
    @ wait for implement
  • 2 列代替整个矩阵
    @ wait for implement
  • 编程语言上的优化技巧
    (1) 先把 String 转成 char[], 以后每次操作都对char[]进行，从9ms到8ms
    (2) 利用boolean[][] 初始化的时候默认为false, 所以初始化的时候一旦不是true就break, 另外就是对map[i][j]更新的时候只对true进行更新

---

小收获

1. 多种可能性的路径探索，如果能够记忆化，就不一定要回溯
2. 两个方向进行，可以抽象成矩阵的两个维度，或许会比用两个指针更方便。

---

To do list

1. dp还有很多可以优化的地方，要继续总结。
2. 尝试把以前做过的dp题都进行优化。

---

参考： http://blog.csdn.net/u011095253/article/details/9248073
http://www.cnblogs.com/boring09/p/4239255.html
http://46aae4d1e2371e4aa769798941cef698.devproxy.yunshipei.com/sunliymonkey/article/details/48165711