Topcoder SRM 689 NonDeterministicSubstring
this problem is about
=========================================================
My approach
1. A>B and
2. Find B length
3. Make all possible String with length of B and push HashSet
4. HashSet will filter duplication.
5. and finally only unique strings remain in hashset
6. compare all string with B if index of character is not ?
7. count all if it is match
my code is below
Problem Statement 

You are given two Strings: A and B. Each character in A
is either '0' or '1'. Each character in B is '0', '1', or '?'. A string C matches B if we can change B into C by changing each '?' in B either to '0' or to '1'. Different occurrences of '?' may be changed to different digits. For example, C = "0101" matches B = "01??". Note that each character in C must be either '0' or '1', there cannot be any '?' remaining. Consider all possible strings that match B. How many of these strings occur as a (contiguous) substring in A? Compute and return their number. Note that we only count each good string once, even if it has multiple occurrences in A. 

Definition 



Limits 



Constraints 

  A will contain between 1 and 50 characters, inclusive.  
  B will contain between 1 and 50 characters, inclusive.  
  Each character in A will be '0' or '1'.  
  Each character in B will be '0', '1' or '?'.  
Examples 

0)  


1)  


2)  


3)  


4)  

=========================================================
My approach
1. A>B and
2. Find B length
3. Make all possible String with length of B and push HashSet
4. HashSet will filter duplication.
5. and finally only unique strings remain in hashset
6. compare all string with B if index of character is not ?
7. count all if it is match
my code is below
public long ways(String A, String B){ HashSet<String> set = new HashSet<String>(); int blen = B.length(); for (int i = 0; i <= A.length()blen; i++) { set.add(A.substring(i, i+blen)); } Iterator<String> iter = set.iterator(); int count =0; while (iter.hasNext()) { String str = iter.next(); boolean found = true; for (int i = 0; i < blen; i++) { if(B.charAt(i)!= '?'){ if(A.charAt(i) != B.charAt(i)){ found =false; break; } } } if(found){ count++; } } return count; }
Comments
Post a Comment