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

The 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!
}
}

According to the order of praise
Caozhy      2016.01.29 08:05

Take the C# to write you a

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 and 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);
}
}
}

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.
WinsenJiansbomber Hey, this is called the word.
WinsenJiansbomber See Dynamic Process
Caozhy DP is a dynamic programming.
Caozhy DP is a dynamic programming.