ตรวจสอบว่าอาร์เรย์สองสตริงเป็นโซลูชัน Leetcode ที่เทียบเท่าหรือไม่


ระดับความยาก สะดวกสบาย
ถามบ่อยใน Facebook
เชือก

ปัญหาตรวจสอบว่าอาร์เรย์สองสตริงเป็นโซลูชัน Leetcode ที่เทียบเท่ากันหรือไม่ให้เราสองคน อาร์เรย์ ของสตริง จากนั้นเราจะบอกให้ตรวจสอบว่าอาร์เรย์สตริงทั้งสองนี้เท่ากันหรือไม่ ความเท่าเทียมกันในที่นี้หมายถึงความจริงที่ว่าถ้าสตริงในอาร์เรย์เชื่อมต่อกัน จากนั้นหลังจากการเชื่อมต่อสตริงทั้งสองจะเท่ากันหรือเหมือนกัน ดังนั้นก่อนที่จะดำน้ำลึกลงไปในการแก้ปัญหาให้เรามาดูตัวอย่างก่อน

ตัวอย่าง

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

คำอธิบาย: อาร์เรย์ทั้งสองสร้าง "abc" ถ้าเราเชื่อมสตริงทั้งหมดเข้าด้วยกัน ดังนั้นพวกเขาจึงเทียบเท่ากัน

ตรวจสอบว่าอาร์เรย์สองสตริงเป็นโซลูชัน Leetcode ที่เทียบเท่าหรือไม่

แนวทางในการตรวจสอบว่าอาร์เรย์สองสตริงเป็นโซลูชัน Leetcode ที่เท่ากันหรือไม่

ปัญหาทำให้เรามีอาร์เรย์ของสตริงสองอาร์เรย์ อาจมีสตริงมากกว่าหนึ่งในสองสตริง แต่เมื่อเรียงต่อกันสตริงผลลัพธ์ทั้งสองจะเหมือนกัน ถ้ามันเหมือนกันเราจะคืนค่าจริงมิฉะนั้นเราจะคืนค่าเท็จ
ตอนนี้วิธีแก้ปัญหาที่ง่ายและใช้งานง่ายคือการสำรวจสตริงทั้งหมดในแต่ละอาร์เรย์ ในขณะที่ข้ามเราเชื่อมสตริงเข้าด้วยกันและสร้างสตริงผลลัพธ์สองสตริง ดังนั้นหลังจากการดำเนินการเชื่อมต่อนี้เราจะตรวจสอบว่าสตริงเหมือนกันหรือไม่ แต่การดำเนินการนี้ต้องการให้เราสร้างสตริง ดังนั้นกระบวนการจึงต้องการพื้นที่เพิ่มเติม แต่เรายังสามารถแก้ปัญหาในสถานที่โดยไม่ต้องใช้พื้นที่เพิ่มเติมได้อีกด้วย
เราจะใช้ตัวแปรสี่ตัวสองตัวสำหรับแต่ละอาร์เรย์ ตัวแปรเหล่านี้จะทำหน้าที่เป็นดัชนีในอาร์เรย์และดัชนีสำหรับสตริง วิธีนี้ทั้งสองจะบอกเราว่าพวกเขาอยู่ที่อักขระ j1th ของสตริง i1th ในอาร์เรย์แรก ในทำนองเดียวกันอักขระ j2th ของสตริง i2th แสดงด้วย i2 และ j2 ตอนนี้สิ่งที่เหลืออยู่คือการนำไปใช้งาน
เราใช้ while loop ภายในซึ่งเราตรวจสอบเงื่อนไขบางประการ หากอักขระปัจจุบันในอาร์เรย์ทั้งสองไม่ตรงกันเราจะส่งคืนเท็จ มิฉะนั้นเราจะตรวจสอบว่าเราอยู่ที่อักขระสุดท้ายของสตริงหรือไม่ หากเป็นเช่นนั้นเราจะเพิ่มดัชนีที่ใช้สำหรับสตริง (i) และตั้งค่าดัชนีอักขระ (j) เป็น 0 มิฉะนั้นเพียงแค่เพิ่ม j ในท้ายที่สุดหากอาร์เรย์ทั้งสองหมดพร้อมกันเราจะคืนค่าจริงหรือไม่ก็เป็นเท็จ

รหัส

รหัส 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 (นาที (N, M)) เนื่องจากเราผ่านแต่ละอักขระของสตริงที่เล็กกว่า ในที่นี้ N และ M แสดงจำนวนอักขระในอาร์เรย์แรกและอาร์เรย์ที่สองตามลำดับ

ความซับซ้อนของอวกาศ

O (1) เนื่องจากเราใช้ตัวแปรจำนวนคงที่