Сравните две двоичные строки, состоящие только из 0 и 1 в Java, хотите выяснить, какая строка лексикографически больше

Question

это то, что я делаю для сравнения двоичной строки, но в худшем случае это занимает o (n) время. Я пытался как вручную, так и методом Strings сравнить, Пожалуйста, помогите мне с лучшим подходом для решения этой проблемы -

по методу CompareTo -

if (A.compareTo(temp) < 0) 
{
    System.out.println("YES");
}
else 
{ 
    System.out.println("NO"); 
}

Перебирая строки: -

for (int k = 0; k < N; k++){
    if (A.charAt(k) == '1' && B.charAt(k) == '0') {
    System.out.println("NO");
    break;
} else if (B.charAt(k) == '1' && A.charAt(k) == '0') {
    System.out.println("YES");
    break;
}

см. Это полный -

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int Q = sc.nextInt();
    String A = sc.next();
    StringBuilder B = new StringBuilder(sc.next());
    for (long i = 0; i < Q; i++) {
        int pos = sc.nextInt();
        B.setCharAt(pos - 1, '1');
        String temp = B.toString();
        if (A.equals(temp)) {
            System.out.println("YES");
        } else {
            for (int k = 0; k < N; k++){
                if (A.charAt(k) == '1' && B.charAt(k) == '0') {
                System.out.println("NO");
                break;
            } else if (B.charAt(k) == '1' && A.charAt(k) == '0') {
                System.out.println("YES");
                break;
            }
        } /*
             * else if (A.compareTo(temp) < 0) { System.out.println("YES");
             * } else { System.out.println("NO"); }
             */
    }
}

Answer 1

Вы делаете два сравнения в каждом условии if. Поскольку гарантируется, что '0'<'1' это может быть упрощено. Кроме того, вам нужно иметь детальное решение, только если два сравниваемых символа не равны.

for (int k = 0; k < N; k++){
    if (A.charAt(k) != B.charAt(k))
    {
        System.out.println(A.charAt(k) < B.charAt(k)? "YES": "NO";
        break;
    }
}