ກວດເບິ່ງວ່າມີ ຄຳ ສັບໃດ ໜຶ່ງ ເກີດຂື້ນເປັນ ຄຳ ນຳ ໜ້າ ຂອງ ຄຳ ສັບໃດ ໜຶ່ງ ໃນ ຄຳ ສັ່ງແກ້ໄຂ Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Yelp
string

ການກວດສອບບັນຫາຖ້າວ່າ ຄຳ ສັບໃດ ໜຶ່ງ ເກີດຂື້ນເປັນ ຄຳ ນຳ ໜ້າ ຂອງ ຄຳ ສັບໃດ ໜຶ່ງ ໃນ ຄຳ ສັ່ງແກ້ໄຂ Leetcode ໄດ້ຂໍໃຫ້ພວກເຮົາຊອກຫາດັດສະນີຂອງ ຄຳ ທີ່ເລີ່ມຕົ້ນດ້ວຍ ຄຳ ຄົ້ນຫາທີ່ໃຫ້. ດັ່ງນັ້ນ, ພວກເຮົາໄດ້ຮັບປະໂຫຍກທີ່ມີບາງອັນ strings ແຍກໂດຍຊ່ອງແລະສາຍອື່ນແມ່ນ ຄຳ ຄົ້ນຫາ. ພວກເຮົາຖືກບອກໃຫ້ຊອກຫາວ່າ ຄຳ ຄົ້ນນີ້ມີຢູ່ເປັນ ຄຳ ນຳ ໜ້າ ຂອງ ຄຳ ໃດ ໜຶ່ງ ໃນປະໂຫຍກ. ຄຳ ສັບດັ່ງກ່າວເກີດຂື້ນເປັນ ຄຳ ນຳ ໜ້າ ໝາຍ ຄວາມວ່າບາງ ຄຳ ຄວນເລີ່ມຕົ້ນດ້ວຍ ຄຳ ທີ່ຄົ້ນຫາ. ຖ້າມີຫລາຍກວ່າ ໜຶ່ງ ຄຳ ທີ່ມີ ຄຳ ທີ່ຄົ້ນຫາເປັນ ຄຳ ນຳ ໜ້າ, ໃຫ້ດັດສະນີທີ່ນ້ອຍທີ່ສຸດ. ສະນັ້ນຕາມປົກກະຕິ, ກ່ອນທີ່ຈະ ດຳ ນ້ ຳ ເລິກເຂົ້າໃນການແກ້ໄຂໃຫ້ພວກເຮົາພິຈາລະນາບາງຕົວຢ່າງ. ພວກເຮົາຖືກບອກໃຫ້ປະຕິບັດຕາມດັດສະນີທີ່ອີງໃສ່ 1 ເມື່ອພວກເຮົາກັບຄືນດັດສະນີ.

ກວດເບິ່ງວ່າມີ ຄຳ ສັບໃດ ໜຶ່ງ ເກີດຂື້ນເປັນ ຄຳ ນຳ ໜ້າ ຂອງ ຄຳ ສັບໃດ ໜຶ່ງ ໃນ ຄຳ ສັ່ງແກ້ໄຂ Leetcode

sentence = "i love eating burger", searchWord = "burg"
4

ຄຳ ອະທິບາຍ: ສາຍ“ burg” ມີຢູ່ໃນ ຄຳ ນຳ ໜ້າ ຂອງ ຄຳ ວ່າ“ burger” ໃນປະໂຫຍກ. ເນື່ອງຈາກວ່າມີພຽງ ຄຳ ດຽວເທົ່ານັ້ນທີ່ມີ ຄຳ ຄົ້ນຫາເປັນ ຄຳ ນຳ ໜ້າ. ພວກເຮົາສົ່ງຄືນດັດສະນີນັ້ນເທົ່ານັ້ນ.

ວິທີການ ສຳ ລັບການກວດສອບຖ້າ ຄຳ ສັບໃດ ໜຶ່ງ ເກີດຂື້ນເປັນ ຄຳ ນຳ ໜ້າ ຂອງ ຄຳ ສັບໃດ ໜຶ່ງ ໃນ ຄຳ ສັ່ງແກ້ໄຂ Leetcode

ການກວດສອບບັນຫາຖ້າວ່າ ຄຳ ສັບໃດ ໜຶ່ງ ເກີດຂື້ນເປັນ ຄຳ ນຳ ໜ້າ ຂອງ ຄຳ ສັບໃດ ໜຶ່ງ ໃນ ຄຳ ສັ່ງແກ້ໄຂ Leetcode ໃຫ້ພວກເຮົາປະໂຫຍກ. ປະໂຫຍກແມ່ນບາງ ຄຳ ທີ່ແຍກອອກຈາກບ່ອນຫວ່າງ. ປະໂຫຍກບໍ່ໄດ້ເລີ່ມຕົ້ນແລະສິ້ນສຸດດ້ວຍພື້ນທີ່ຫວ່າງ. ພວກເຮົາຍັງໄດ້ຮັບສາຍຫລື ຄຳ ສັບອື່ນນອກ ເໜືອ ຈາກປະໂຫຍກນີ້ທີ່ຕ້ອງການຄົ້ນຫາໃນປະໂຫຍກ. ພວກເຮົາຖືກບອກໃຫ້ສົ່ງຄືນດັດສະນີທີ່ນ້ອຍທີ່ສຸດຂອງ ຄຳ ທີ່ມີ ຄຳ ຄົ້ນຫາທີ່ເປັນ ຄຳ ນຳ ໜ້າ ຂອງມັນ. ສະນັ້ນເພື່ອແກ້ໄຂບັນຫາບໍ່ວ່າຈະເປັນພວກເຮົາແບ່ງສາຍຕາມຊ່ອງຫວ່າງ. ຫຼັງຈາກນັ້ນ, ພຽງແຕ່ຂ້າມຜ່ານຄໍາສັບຕ່າງໆແລະກວດເບິ່ງວ່າຄໍາທີ່ໃຊ້ໃນປະຈຸບັນເລີ່ມຕົ້ນດ້ວຍຄໍາຄົ້ນຫາຫລືບໍ່. ການປະຕິບັດການ ດຳ ເນີນງານນີ້ແມ່ນງ່າຍດາຍໃນ Java ດ້ວຍການແບ່ງປັນ ຄຳ ສັບ () ແລະ startwith ().

ວິທີອື່ນໃນການແກ້ໄຂບັນຫາແມ່ນການເພີ່ມພື້ນທີ່ໃຫ້ກັບປະໂຫຍກໃນຕອນເລີ່ມຕົ້ນ. ຫລັງຈາກນັ້ນ, ໃຊ້ທັງ ໜ້າ ທີ່ find () ຫລືໃຊ້ KMP algorithm ເພື່ອຄົ້ນຫາວ່າມີ ຄຳ ໃດທີ່ມີ ຄຳ ຄົ້ນຫາຂອງພວກເຮົາເປັນ ຄຳ ນຳ ໜ້າ.

ລະຫັດໃນການກວດສອບຖ້າ ຄຳ ສັບໃດ ໜຶ່ງ ເກີດຂື້ນເປັນ ຄຳ ນຳ ໜ້າ ຂອງ ຄຳ ສັບໃດ ໜຶ່ງ ໃນ ຄຳ ສັ່ງແກ້ໄຂ Leetcode

ລະຫັດ C ++

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

int isPrefixOfWord(string sentence, string searchWord) {
    string newSentence = " " + sentence, word = " " + searchWord;
    auto pos = newSentence.find(word);
    if (pos != string::npos)
        return count(begin(newSentence), begin(newSentence) + pos + 1, ' ');
    return -1;
}

int main(){
    string sentence = "i love eating burger";
    string searchWord = "burg";
    cout<<isPrefixOfWord(sentence, searchWord);
}
4

ລະຫັດ Java

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

class Rough {
    public static int isPrefixOfWord(String sentence, String searchWord) {
        String[] words = sentence.split(" ");
        for (int i = 1; i <= words.length; ++i) {
            if (words[i - 1].startsWith(searchWord)) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) throws IOException {
        String sentence = "i love eating burger";
        String searchWord = "burg";

        System.out.print(isPrefixOfWord(sentence, searchWord));
    }
}
4

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

ໂອ (N), ເນື່ອງຈາກວ່າພວກເຮົາ traverse ໃນໄລຍະທັງຫມົດຂອງປະໂຫຍກໃນກໍລະນີຮ້າຍແຮງທີ່ສຸດ. ດັ່ງນັ້ນຄວາມສັບສົນທີ່ໃຊ້ເວລາແມ່ນເປັນເສັ້ນ.

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (N), ໃນທັງສອງວິທີແກ້ໄຂພວກເຮົາສ້າງຂບວນ ໃໝ່ ຫລືສາຍ ໃໝ່ ທີ່ໃຊ້ເວລາຫວ່າງໃຫ້ພວກເຮົາ.