在字符串中查找子序列

Question

我一直在解决 Hackerrank 上的这组挑战，link : Hackerrank in a String

我想出了我的算法，它是这样的：

To check whether it has atleast two a's, r's and k's according to the hackerrank string

Check that it contains following chars h, a, c, k, e, r, n, k

let p[0], p(1), p[2].....,p[9] be the respective indices of h, a, c, k, e, r, r, a, n, k in string . If p[0] < p(1) < p[2] < .... < p[9] is true, then contains hackerrank.

我知道这很糟糕，由于这个错误也没有输出：Terminated due to timeout

代码：

我有一个名为 hackerrankInString(String s) 的方法，它 returns "YES" 或 "NO" string

// Complete the hackerrankInString function below.
static String hackerrankInString(String s) {
  int countR = 0, countA = 0, countK = 0;
  //for reading multi-line inputs, it will perform operation individually 
  // on the inputs
  while(scanner.hasNextLine()){
    for(int i=0; i < s.length(); i++){
      if(s.charAt(i) == 'r')
        countR++;

      if(s.charAt(i) == 'a')
        countA++;

      if(s.charAt(i) == 'k')
        countK++;
    }

    //It should atleast have two As, two Rs, and two Ks
    if(countR >= 2 && countA >= 2 && countK >= 2){
      //If the string contains hackerrank
      if(s.contains(Character.toString('h')) && s.contains(Character.toString('a'))  && s.contains(Character.toString('c')) && s.contains(Character.toString('k')) && s.contains(Character.toString('e')) && s.contains(Character.toString('r')) &&    s.contains(Character.toString('n'))){
          if((s.indexOf('h') > s.indexOf('a')) && (s.indexOf('h') > s.indexOf('c')) && (s.indexOf('h') > s.indexOf('k')) && (s.indexOf('h') > s.indexOf('e')) && (s.indexOf('h') > s.indexOf('r')) && (s.indexOf('h') > s.lastIndexOf('r')) && (s.indexOf('h') > s.lastIndexOf('a')) && (s.indexOf('h') > s.indexOf('n')) && (s.indexOf('h') > s.lastIndexOf('k'))){
              if((s.indexOf('a') > s.indexOf('c')) && (s.indexOf('a') > s.indexOf('k')) && (s.indexOf('a') > s.indexOf('e')) && (s.indexOf('a') > s.indexOf('r')) && (s.indexOf('a') > s.lastIndexOf('r')) && (s.indexOf('a') > s.lastIndexOf('a')) && (s.indexOf('a') > s.indexOf('n')) && (s.indexOf('a') > s.lastIndexOf('k'))){
                  if((s.indexOf('c') > s.indexOf('k')) && (s.indexOf('c') > s.indexOf('e')) && (s.indexOf('c') > s.indexOf('r')) && (s.indexOf('c') > s.lastIndexOf('r')) && (s.indexOf('c') > s.lastIndexOf('a')) && (s.indexOf('c') > s.indexOf('n')) && (s.indexOf('c') > s.lastIndexOf('k'))){
                      if((s.indexOf('k') > s.indexOf('e')) && (s.indexOf('k') > s.indexOf('r')) && (s.indexOf('k') > s.lastIndexOf('r')) && (s.indexOf('k') > s.lastIndexOf('a')) && (s.indexOf('k') > s.indexOf('n')) && (s.indexOf('k') > s.lastIndexOf('k'))){
                        if((s.indexOf('e') > s.indexOf('r')) && (s.indexOf('e') > s.lastIndexOf('r')) && (s.indexOf('e') > s.lastIndexOf('a')) && (s.indexOf('e') > s.indexOf('n')) && (s.indexOf('e') > s.lastIndexOf('k'))){
                            if((s.indexOf('r') > s.lastIndexOf('r')) && (s.indexOf('r') > s.lastIndexOf('a')) && (s.indexOf('r') > s.indexOf('n')) && (s.indexOf('r') > s.lastIndexOf('k'))){
                                if((s.lastIndexOf('r') > s.lastIndexOf('a')) && (s.lastIndexOf('r') > s.indexOf('n')) && (s.lastIndexOf('r') > s.lastIndexOf('k'))){
                                    if((s.lastIndexOf('a') > s.indexOf('n')) && (s.lastIndexOf('a') > s.lastIndexOf('k'))){
                                        if(s.indexOf('n') > s.lastIndexOf('k')){
                                            return "YES";
                                        }
                                    }
                                }
                            }
                        }
                      }
                  }
              }
          }
        }
      }
    }

    return "NO";
}

请帮帮我，我想学两个东西，

如何解决这个挑战
如何有效地解决我的第三个算法语句

如有任何帮助，我们将不胜感激。

Answer 1

没有太多时间检查，但可能看起来像那样

public static String solve(String startWord, String givenWord) {
    for(int i = 0; i < startWord.length(); i++) {
        String letter = startWord.substring(i, i + 1);
        int index = givenWord.indexOf(letter);
        if(index == -1) {
            return "NO";
        } else {
            givenWord = givenWord.substring(index + 1, givenWord.length());
        }
    }

    return "YES";
}

Answer 2

您可以使用正则表达式来解决问题：

static String hackerrankInString(String input) {
    final String regexHack = ".*h.*a.*c.*k.*e.*r.*r.*a.*n.*k.*";
    return input.matches(regexHack) ? "YES" : "NO";
}

使用以下方式调用它：

System.out.println(hackerrankInString("hhaacckkekraraannk"));  // YES
System.out.println(hackerrankInString("hackerworld"));         // NO

您可以试试正则表达式 here。

在字符串中查找子序列

Find Subsequence in a String

java

character-encoding

subsequence