Проверьте, являются ли два массива строк эквивалентным решением Leetcode  


Сложный уровень Легко
Часто спрашивают в Facebook
алгоритмы кодирование Интервью подготовка к собеседованию LeetCode LeetCodeSolutions строка

Проблема Проверка эквивалентности двух строковых массивов Решение Leetcode предоставляет нам два массивы струн. Затем нам предлагается проверить, эквивалентны ли эти два строковых массива. Эквивалентность здесь относится к тому факту, что если строки в массивах объединены. Тогда после конкатенации обе строки будут равны или одинаковы. Итак, прежде чем углубляться в решение, давайте сначала рассмотрим несколько примеров.

Примеры  

word1[] = {"ab", "c"}
word2[] = {"a", "bc"}
true

Объяснение: Оба массива образуют «abc», если мы объединяем все строки. Итак, они эквивалентны.

Проверьте, являются ли два массива строк эквивалентным решением Leetcodeшпилька

Подход к проверке, являются ли два массива строк эквивалентным решением Leetcode  

Задача дала нам два массива строк. В одной из двух струн может быть больше, чем в другой. Но при объединении обе результирующие строки будут одинаковыми. Если они совпадают, мы возвращаем true, иначе мы возвращаем false.
Теперь простое и легкое в реализации решение - просто пройти по всем строкам в каждом из массивов. Во время обхода мы объединяем строки и создаем две результирующие строки. Итак, после этой операции конкатенации мы проверим, совпадают ли строки. Но эта операция требует от нас создания строк. Таким образом, процессу требуется дополнительное пространство. Но мы также можем решить проблему в любом месте, не занимая лишнего места.
Мы будем использовать четыре переменные, по две для каждого массива. Эти переменные будут действовать как индексы в массиве, а затем как индексы для строки. Таким образом, двое из них скажут нам, что они находятся у j1-го символа i1-й строки в первом массиве. Точно так же j2-й символ i2-й строки представлен i2 и j2. Теперь все, что осталось, - это реализация.
Мы используем в то время как цикл внутри которого мы проверяем несколько условий. Если текущий символ в обоих массивах не совпадает, мы возвращаем false. иначе мы проверяем, находимся ли мы на последнем символе строки. В этом случае мы увеличиваем индекс, используемый для строки (i), и устанавливаем индекс символа (j) равным 0. В противном случае просто увеличиваем j. В конце концов, если оба массива исчерпаны одновременно, мы возвращаем true, иначе false.

Смотрите также
Преобразование Postfix в Infix

Код:  

Код C ++ для проверки, эквивалентны ли два строковых массива решению Leetcode

#include <bits/stdc++.h>
using namespace std;

bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
    int i1 = 0, j1 = 0, i2 = 0, j2 = 0;
    while(true){
        if(word1[i1][j1] != word2[i2][j2]) return false;
        if(j1 == word1[i1].size()-1)i1++, j1 = 0;
        else j1++;
        if(j2 == word2[i2].size()-1)i2++, j2 = 0;
        else j2++;
        if(i1 == word1.size() && i2 == word2.size())
            return true;
        else if(i1 == word1.size() || i2 == word2.size())
            return false;
    }
}

int main() {
  vector<string> word1 = {"ab", "c"};
  vector<string> word2 = {"a", "bc"};
  cout<<(arrayStringsAreEqual(word1, word2) ? "true" : "false");
  return 0;
}
true

Код Java для проверки, эквивалентны ли два строковых массива решению Leetcode

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static boolean arrayStringsAreEqual(String[] word1, String[] word2) {
        int i1 = 0, j1 = 0, i2 = 0, j2 = 0;
        while(true){
            if(word1[i1].charAt(j1) != word2[i2].charAt(j2)) return false;
            if(j1 == word1[i1].length()-1){i1++; j1 = 0;}
            else j1++;
            if(j2 == word2[i2].length()-1){i2++; j2 = 0;}
            else j2++;
            if(i1 == word1.length && i2 == word2.length)
                return true;
            else if(i1 == word1.length || i2 == word2.length)
                return false;
        }
    }

  public static void main (String[] args) throws java.lang.Exception
  {
    String[] word1 = {"ab", "c"};
    String[] word2 = {"a", "bc"};
    System.out.print((arrayStringsAreEqual(word1, word2) ? "true" : "false"));
    return 0;
  }
}
true

Анализ сложности  

Сложность времени

O (min (N, M)), потому что мы перебираем каждый символ меньшей строки. Здесь N и M представляют количество символов в первом и втором массивах соответственно.

Космическая сложность

O (1), потому что мы использовали постоянное количество переменных.

 

1