2 Weiwei niunuan 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/thread-145290-1-1.html

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

The 7 answer

Caozhy
Caozhy   Ds   Rxr 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
Caozhy   Ds   Rxr 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
Caozhy   Ds   Rxr 2016.01.29 08:06

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

Caozhy
Caozhy   Ds   Rxr 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
Caozhy   Ds   Rxr 2016.01.29 08:29
String S1 = "aaaaaa";
String S2 = "a+a-";

output
0,2
One
Press any key to continue.

WinsenJiansbomber
WinsenJiansbomber   2016.01.29 08:57

I didn't know what to DP!

Caozhy
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
WinsenJiansbomber Hey, this is called the word.
About a month ago reply
Caozhy
Caozhy Reply Jimbo: Dynamic Programming
About a month ago reply
WinsenJiansbomber
WinsenJiansbomber See Dynamic Process
About a month ago reply
Caozhy
Caozhy DP is a dynamic programming.
About a month ago reply
Caozhy
Caozhy DP is a dynamic programming.
About a month ago reply
91program
91program   Ds   Rxr 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

91program
91program Caozhy: I just showed a kind of possible, and LZ said clearly don't know what is the relationship?
About a month ago reply
91program
91program This can explain what caozhy: reply! Is that the examiner is not seen?
About a month ago reply
Caozhy
Caozhy The program is wrong, not the last test case. LZ said very clearly.
About a month ago reply
Csdn user default icon
Upload...
Upload photo
Insert a picture