Weiwei_niunuan2016.01.29 07:08 questions
 IT interview questions with online DP code would hang the correct DP how to write

The interviewer gave me a teacher, I used an acre of ground DP solution, sources are as follows
Http://www.1point3acres.com/bbs/thread14529011.htmlThe topic is as follows:
String S1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";
String S2 = "a+b+c";S2 is a letter symbol, plus representatives have two in front of the characters, minus representative has four, also is to say S2 is actually "aabbcccc", do not consider the invalid.
In S1, to find out the continuous or discontinuous S2, that is to say from the S1 to find "AA....bb.....Cccc, ABC order can not be changed, can have zero or more characters but, return the total number. In the above example, there are four.
The test results of sln.findMatches ("aaaaaa", "a+a"), the results of 0, no, hang
In addition System.out.println (sln.findMatches ("waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c+c"); 5) ran out, feeling right results should be 2
Don't know what should be dp with the correct answer? Someone can give the correct DP code?The following is from the test case not copy the code:
Public class {Solution Public int findMatches (String S1, String S2) { Int = s1.length (len1), len2 (= s2.length); If (len2 > len1) return 0; If (len2 = 0  len2%2! = 0) return 0; Matches each pattern / / DP Of matches between s1.substring / / number (0, I + 1) and s2.substring (J * 2, J * 2 + 2) Int[][] DP = new int[len1 + 1][len2 / 1] + 2; Match for dp[0][j] / / no 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! } }
The 7 answer
 Caozhy 2016.01.29 08:05
 Has adopted
Take the C# to write you a
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 and 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 2016.01.29 07:42
Too tired, do not write code, think of your ideas, to find out almost all single (starting at index) in an array and then they get increasing combination of permutation and combination.
 Caozhy 2016.01.29 08:06
10,20,28
10,20,64
10,56,64
41,56,64
Four
Press any key to continue.
 Caozhy 2016.01.29 08:09
In addition System.out.println (sln.findMatches ("waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c+c"); 5) ran out, feeling right results should be 2
Is 5
(each number represents a matching subscript)
10,20,24,30
10,20,24,66
10,20,30,66
10,20,31,66
10,20,32,66
Five
Press any key to continue.
 Caozhy 2016.01.29 08:29
String S1 = "aaaaaa";
String S2 = "a+a";
output
0,2
One
Press any key to continue.
 WinsenJiansbomber 2016.01.29 08:57
I didn't know what to DP!
 Caozhy The word Jimbo: can reply? I say you are spirit, I praise you. I say you are nervous, I just scold you.
 About a month ago reply
 WinsenJiansbomber Hey, this is called the word.
 About a month ago reply
 WinsenJiansbomber See Dynamic Process
 About a month ago reply
 91program 2016.01.29 09:15
The direct use of an acre of ground DP answer to answer, hang up the estimation before you have seen the examiner is your answer