My Blog List

Thursday, April 28, 2016

Topcoder SRM 689 NonDeterministicSubstring

this problem is about


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

    
Class: NonDeterministicSubstring
Method: ways
Parameters: String, String
Returns: long
Method signature: long ways(String A, String B)
(be sure your method is public)

Limits

    
Time limit (s): 2.000
Memory limit (MB): 256
Stack limit (MB): 256

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)
    
"00010001"
"??"
Returns: 3
There are four strings that match B: the strings "00", "01", "10", and "11". Out of these, the string "11" does not occur in A as a substring. The other three do occur, hence the answer is 3.
1)
    
"00000000"
"??0??0"
Returns: 1
There are 16 different strings that match B, but out of those only the string "000000" is a substring of A.
2)
    
"001010101100010111010"
"???"
Returns: 8
Each of the 8 strings that match B occurs somewhere in A.
3)
    
"00101"
"??????"
Returns: 0
Here, the length of B is greater than the length of A. Clearly, a string that matches this B cannot be a substring of this A.
4)
    
"1101010101111010101011111111110001010101"
"???????????????????????????????????"
Returns: 6


=========================================================
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;
 }

No comments:

Post a Comment