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; }
No comments:
Post a Comment