2016-01-28 23:08

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

String s1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";
String s2 = "a+b+c-";

s2的形式是一个字母加上一个符号，正号代表有两个前面的字符，负号代表有四个，也就是说s2其实是"aabbcccc"，不考虑invalid。

`````` 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!
}
}
``````
• 点赞
• 写回答
• 关注问题
• 收藏
• 邀请回答

#### 6条回答默认 最新

• blownewbee 2016-01-29 00:05
已采纳

拿C#给你写了一个

`````` using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

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])
{
}
}
}
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);
}
}
}

``````
点赞 打赏 评论
• blownewbee 2016-01-28 23:42

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

点赞 打赏 评论
• blownewbee 2016-01-29 00:06

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

点赞 打赏 评论
• blownewbee 2016-01-29 00: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 . . .

点赞 打赏 评论
• blownewbee 2016-01-29 00:29
``````        string s1 = "aaaaaa";
string s2 = "a+a-";
``````

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

点赞 打赏 评论
• 91program 2016-01-29 01:15

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

点赞 打赏 评论