2 weiwei niunuan weiwei_niunuan 于 2016.01.29 07:08 提问

IT公司面试题 用网上的dp代码 挂了 请问正确的dp该怎么写

面试官给我出了道老题, 我用了一亩三分地上的dp解答,来源如下
http://www.1point3acres.com/bbs/thread-145290-1-1.html

题目如下:
String s1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";
String s2 = "a+b+c-";

s2的形式是一个字母加上一个符号,正号代表有两个前面的字符,负号代表有四个,也就是说s2其实是"aabbcccc",不考虑invalid。
在s1中,找出连续或者不连续的s2,也就是说从s1中找出"aa....bb.....cccc",abc顺序不能变,但是之间可以有零个或多个字符,返回共有多少个。在上面这个例子中,有四个。
结果测试sln.findMatches("aaaaaa", "a+a-") ,出来结果为0,不对,挂了
另外System.out.println(sln.findMatches("waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c+c-")); 跑出来是5,感觉正确结果应该是2
不知道用dp正确的解答应该是什么?有人能给出正确的dp代码吗?

以下是从拷贝的测试用例不通过的代码:

 public class Solution {
        public int findMatches(String s1, String s2){
       int len1 = s1.length(), len2 = s2.length();
       if (len2 > len1) return 0;
       if (len2 == 0 || len2 %2 != 0) return 0;
       // DP matches each pattern
       // number of matches between s1.substring(0, i + 1) and s2.substring(j * 2, j * 2 + 2)
       int[][] dp = new int[len1 + 1][len2 / 2 + 1];
       // no match for dp[0][j]
       for (int i = 1; i < len1; i++){
           dp[i + 1][0] = 1;
           for (int j = 0; j < len2 / 2; j++){
               dp[i + 1][j + 1] = dp[i][j + 1];
               if (isMatch(s1, s2, i, j)){
                   if (s2.charAt(2*j + 1) == '+')
                       dp[i + 1][j + 1] += dp[i - 1][j];
                   else
                       dp[i + 1][j + 1] += dp[i - 3][j];
               }
           }
       }
       return dp[len1][len2 / 2];
  }

   boolean isMatch(String s1, String s2, int i, int j){
       char c = s2.charAt(j * 2);
       char p = s2.charAt(j * 2 + 1);
       int len = p == '+' ? 2 : 4;
       if (i - len < -1) return false;
       for (int h = i - len + 1; h <= i; h++){
           if (s1.charAt(h) != c) return false;
       }
       return true;
   }

   public static void main(String[] args){
           Solution sln = new Solution();

           System.out.println(sln.findMatches("waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c-"));  // 4

           System.out.println(sln.findMatches("waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c+c-")); // 5 ???  I think it should be 2
           System.out.println(sln.findMatches("aaaaaa", "a+a-"));//0  wrong!
   }
}

7个回答

caozhy
caozhy   Ds   Rxr 2016.01.29 08:05
已采纳

拿C#给你写了一个

 using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string s1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";
            string s2 = "a+b+c-";
            List<string> list = new List<string>();
            for (int i = 0; i < s2.Length; i += 2)
            {
                list.Add(new string(s2[i], s2[i + 1] == '+' ? 2 : 4));
            }
            List<List<int>> idx = list.Select(x => new List<int>()).ToList();
            for (int i = 0; i < s1.Length; i++)
            {
                for (int j = 0; j < list.Count; j++)
                {
                    if (i <= s1.Length - list[j].Length && s1.Substring(i, list[j].Length) == list[j])
                    {
                        idx[j].Add(i);
                    }
                }
            }
            List<List<int>> result = idx[0].Select(x => new List<int>() { x }).ToList();
            for (int i = 1; i < idx.Count; i++)
            {
                result = result.SelectMany(x => idx[i].Where(y => y >= x.Last() + list[i - 1].Length).Select(y => x.Concat(new int[] { y }).ToList())).ToList();
            }
            foreach (var item in result) Console.WriteLine(string.Join(",", item));
            Console.WriteLine(result.Count);
        }
    }
}

caozhy
caozhy   Ds   Rxr 2016.01.29 07:42

太困了,代码不写了,觉得你的思路差不多,先找出所有的单个的匹配(开始的索引)放入数组,然后将它们排列组合,取得递增的组合。

caozhy
caozhy   Ds   Rxr 2016.01.29 08:06

10,20,28
10,20,64
10,56,64
41,56,64
4
Press any key to continue . . .

caozhy
caozhy   Ds   Rxr 2016.01.29 08:09

另外System.out.println(sln.findMatches("waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c+c-")); 跑出来是5,感觉正确结果应该是2
就是5
(每个数字代表一个匹配的下标)

10,20,24,30
10,20,24,66
10,20,30,66
10,20,31,66
10,20,32,66
5
Press any key to continue . . .

caozhy
caozhy   Ds   Rxr 2016.01.29 08:29
        string s1 = "aaaaaa";
        string s2 = "a+a-";

输出
0,2
1
Press any key to continue . . .

WinsenJiansbomber
WinsenJiansbomber   2016.01.29 08:57

竟然不知DP为何物!

caozhy
caozhy 回复Jimbo: 一字能差么?我说你很精神,我是夸你。我说你是神经,我就是骂你了。
接近 2 年之前 回复
WinsenJiansbomber
WinsenJiansbomber 嘿嘿,這個叫做一字之差麼
接近 2 年之前 回复
caozhy
caozhy 回复Jimbo: Dynamic Programming
接近 2 年之前 回复
WinsenJiansbomber
WinsenJiansbomber 明白 Dynamic Process
接近 2 年之前 回复
caozhy
caozhy dp就是动态规划。
接近 2 年之前 回复
caozhy
caozhy dp就是动态规划。
接近 2 年之前 回复
91program
91program   Ds   Rxr 2016.01.29 09:15

直接用一亩三分地上的dp解答来解答,挂了估计是考官在你之前已经看过你给的答案

91program
91program 回复caozhy: 我只是说明了一种可能,和 LZ 说的清楚不清楚有什么关系呢?
接近 2 年之前 回复
91program
91program 回复caozhy: 这又能说明什么!难道能说明考官就没有看过?
接近 2 年之前 回复
caozhy
caozhy 那个程序是错的,没有通过最后一个测试用例。lz说的很清楚。
接近 2 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!