## Tuesday, September 16, 2014

### 包子IT面试培训 助你拿到理想的offer!

[例题1]

Given a string of 1, 0 or ?, return all the matching strings that ? could be either 0 or 1.

For example,

input : 1??

output: {100, 101, 110, 111}.

input: 100100?00?

output: {1001000000,1001000001,1001001000,1001001001}

[思路1]

[代码1]
```public static void returnAll(String input) {
if(input == null || input.isEmpty()) {
return;
}

StringBuilder current_string = new StringBuilder();
returnAllRecursion(input, 0, current_string);
}

public static void returnAllRecursion(String input, int current_location, StringBuilder current_string){
if (input.length() == current_location) {
System.out.println(current_string);
return;
}

while (input.length() > current_location && input.charAt(current_location) != '?') {
current_string.append(input.charAt(current_location));
current_location++;
}

if (input.length() == current_location) {
System.out.println(current_string);
current_string.deleteCharAt(current_location - 1);
return;
}

if (input.charAt(current_location) == '?') {
current_string.append(0);
returnAllRecursion(input, current_location + 1, current_string);
current_string.deleteCharAt(current_string.length() - 1);
current_string.append(1);
returnAllRecursion(input, current_location + 1, current_string);
current_string.deleteCharAt(current_string.length() - 1);
}
}

public static void main(String[] args) {
returnAll("0100");
System.out.println("---------------");
returnAll("01??");
System.out.println("---------------");
returnAll("???0");
System.out.println("---------------");
returnAll("????");
}

```

[思路2]

[代码2]
```public static void returnAllUsingStack(String input) {
if(input == null || input.isEmpty()){
return;
}

Stack positionToReVisit = new Stack();
positionToReVisit.push(-1);

StringBuilder currentString = new StringBuilder();
int currStartPosition = 0;

for (int i = 0; i < input.length(); i++) {
if (input.charAt(i) == '?') {
positionToReVisit.push(i);
currentString.append(0);
break;
}
currentString.append(input.charAt(i));
currStartPosition++;
}

if (currentString.length() == input.length()) {
System.out.println(currentString);
return;
}

while (!positionToReVisit.isEmpty()) {
for (int i = currStartPosition + 1; i < input.length(); i++) {
if (input.charAt(i)== '?') {
currentString.append('0');
positionToReVisit.push(i);
} else {
currentString.append(input.charAt(i));
}
}

if (currentString.length() == input.length()) {
System.out.println(currentString);
}

currStartPosition = positionToReVisit.pop();

if (currStartPosition == -1) break;

currentString = new StringBuilder(currentString.substring(0, currStartPosition));
currentString.append('1');
}

return;
}```

[思路3]

[代码3]

```public static void matchingQuestionMark(String s) {
if (s == null || s.isEmpty()) return;

List questionMarkIndex = new ArrayList();
int totalQuestionMarkCount = 0;

for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == '?') {
totalQuestionMarkCount++;
}
}

if (totalQuestionMarkCount == 0) return;

for (int i = 0; i < (1 << totalQuestionMarkCount); i++) {
StringBuilder sb = new StringBuilder(s);
int j = 0;
int temp = i;
while (j < totalQuestionMarkCount) {
int index = questionMarkIndex.get(j);
if ((temp & 1) == 0) {
sb.replace(index, index + 1, "0");
} else {
sb.replace(index, index + 1, "1");
}
j++;
temp = temp >> 1;

}
System.out.println(sb.toString());
}
}
```