活跃农民
- 积分
- 480
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2015-7-20
- 最后登录
- 1970-1-1
|
- class Solution {
- private int[] pattern;
- private String str;
- private int count = 0;
-
- public int countValidCombinations(int[] pattern, String str) {
- this.pattern = pattern;
- this.str = str;
- backtrack(0, 0, 0);
- return count;
- }
-
- private void backtrack(int strIndex, int patternIndex, int currentFCount) {
- // Base case: reached end of string
- if (strIndex == str.length()) {
- // Valid only if we've used all patterns and current F count is 0
- if (patternIndex == pattern.length && currentFCount == 0) {
- count++;
- }
- return;
- }
-
- // If current F count matches pattern number, must use W
- if (currentFCount > 0 && patternIndex < pattern.length &&
- currentFCount == pattern[patternIndex]) {
- if (str.charAt(strIndex) != 'F') {
- backtrack(strIndex + 1, patternIndex + 1, 0);
- }
- return;
- }
-
- // If current F count exceeds pattern number, invalid path
- if (patternIndex < pattern.length && currentFCount > pattern[patternIndex]) {
- return;
- }
-
- char currentChar = str.charAt(strIndex);
- if (currentChar == '?') {
- // Try F
- backtrack(strIndex + 1, patternIndex, currentFCount + 1);
- // Try W
- if (currentFCount == 0 ||
- (patternIndex < pattern.length && currentFCount == pattern[patternIndex])) {
- backtrack(strIndex + 1, currentFCount == 0 ? patternIndex : patternIndex + 1, 0);
- }
- } else if (currentChar == 'F') {
- backtrack(strIndex + 1, patternIndex, currentFCount + 1);
- } else { // currentChar == 'W'
- if (currentFCount == 0 ||
- (patternIndex < pattern.length && currentFCount == pattern[patternIndex])) {
- backtrack(strIndex + 1, currentFCount == 0 ? patternIndex : patternIndex + 1, 0);
- }
- }
- }
-
- public static void main(String[] args) {
- testCase1();
- testCase2();
- testCase3();
- testCase4();
- }
-
- private static void testCase1() {
- Solution solution = new Solution();
- int[] pattern = {1, 3, 2};
- String str = "FW?FF??W";
- int result = solution.countValidCombinations(pattern, str);
- System.out.println("Test Case 1: " + result);
- // Expected: pattern matches like "FWFFF??W" where ? can be F or W
- }
-
- private static void testCase2() {
- Solution solution = new Solution();
- int[] pattern = {1};
- String str = "F?W";
- int result = solution.countValidCombinations(pattern, str);
- System.out.println("Test Case 2: " + result);
- // Expected: 1 (only "FWW" is valid)
- }
-
- private static void testCase3() {
- Solution solution = new Solution();
- int[] pattern = {2};
- String str = "FF?";
- int result = solution.countValidCombinations(pattern, str);
- System.out.println("Test Case 3: " + result);
- // Expected: 1 (only "FFW" is valid)
- }
-
- private static void testCase4() {
- Solution solution = new Solution();
- int[] pattern = {1, 1};
- String str = "F?F?";
- int result = solution.countValidCombinations(pattern, str);
- System.out.println("Test Case 4: " + result);
- // Expected: 1 (only "FWFW" is valid)
- }
- }
复制代码 |
|