모든 단어가 연결된 부분 문자열

난이도 하드
자주 묻는 질문 아마존 드 쇼
해싱 끈 두 포인터조회수 39
링크드 인버퍼레딧텀블러

모든 단어 문제를 연결하는 부분 문자열에서 우리는 현 s 및 목록은 각각 길이가 같은 여러 단어로 구성됩니다. 목록에있는 모든 단어를 임의의 순서로 연결 한 결과 일 수있는 부분 문자열의 시작 색인을 인쇄합니다.

핀

모든 단어가 연결된 부분 문자열에 대한 설명

문자열 s = "capcodthecodcap"및 주어진 목록 L = [ "cap", "cod"]

주어진 목록의 모든 단어를 연결합니다. 주어진 목록의 모든 단어를 연결하는 모든 가능한 조합은 다음과 같습니다.

  • 캡코드
  • 대구

이제 주어진 문자열에서 연결된 문자열의 시작 인덱스를 검색합니다.

주어진 문자열 "에서"capcod "하위 문자열의 시작 인덱스캡코드thecodcap”은 0입니다.

주어진 문자열“capcodthe”에서 하위 문자열“codcap”의 시작 인덱스대구"는 9입니다.

따라서 출력은 0과 9가됩니다.

예

입력: 

s =“capcodthecodcap”

L = [ "cap", "cod"]

출력:

0 9

입력: 

s =“heythejenna”

L = [ "헤이", "더"]

출력:

0

암호알고리즘

  1. 길이가 n 인 문자열 s와 주어진 문자열과 같은 길이의 단어 목록을 초기화합니다.
  2. 지도와 임시지도를 초기화합니다.
  3. 그 후에 주어진 목록의 모든 단어를 연결하는 길이와 동일한 길이의 가능한 모든 하위 문자열을 탐색하십시오.
  4. 가능한 모든 하위 문자열을 사용하여 새 맵을 이전 맵과 연결합니다.
  5. 하위 문자열의 단어가 새 맵에 있는지 확인하고 개수를 1만큼 줄인 다음 루프를 끊습니다.
  6. 새지도를 가로 질러 모든 단어의 개수가 0보다 작은 지 확인하고 목록 / 배열 해상도를 반환합니다.
  7. 반환 된 목록 / 배열을 탐색하고 저장된 모든 값을 인쇄합니다.

모든 단어를 연결하여 부분 문자열을 찾는 C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
  
vector<int> Substring(string s, const vector<string>& L){ 
  
    int size = L[0].size(); 
  
    int count = L.size(); 
  
    int length = size * count; 
  
    vector<int> res; 
  
    if(length>s.size()) 
        return res; 
  
    unordered_map<string, int> hash_map; 
  
    for(int i=0; i<count; i++)  
        hash_map[L[i]]++;     
  
    for(int i=0; i<=s.size()-length; i++) { 
        unordered_map<string, int> temp_hash_map(hash_map); 
  
        int j = i,c=count; 
  
        while(j<i+length){ 
  
            string word = s.substr(j, size); 
  
  
            if(hash_map.find(word) == hash_map.end()||temp_hash_map[word]==0) 
                break; 
  
            else{ 
                temp_hash_map[word]--;
                c--;
            }  
            j += size; 
        } 
       
        if(c == 0) 
            res.push_back(i); 
    } 
  
    return res; 
} 
  
int main(){ 
    string s = "capcodthecodcap"; 
    vector<string> L = { "cap", "cod" }; 
    vector<int> indices = Substring(s, L); 
    for(int i=0; i<indices.size(); i++) 
        cout<<indices[i]<<" "; 
    return 0; 
}
0 9

모든 단어를 연결하여 하위 문자열을 찾는 Java 프로그램

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.HashMap; 
import java.util.List;

class sub{
    
    public static ArrayList<Integer>Substring(String s, final List<String> L){ 
  
        int size = L.get(0).length(); 
         
        int count = L.size(); 
  
        int length = size * count; 
  
        ArrayList<Integer> res = new ArrayList<Integer>(); 
        int n = s.length(); 
          
        if(length > n){ 
            return res; 
        } 
  
        HashMap<String, Integer> hashMap = new HashMap<String, Integer>(); 
  
        for(String word : L){ 
            hashMap.put(word, hashMap.getOrDefault(word, 0) + 1); 
        } 
  
          
        for(int i=0; i<=n-length; i++){ 
            HashMap<String, Integer> tempMap = (HashMap<String, Integer>) hashMap.clone(); 
            int j = i, c = count; 
              
            while(j<i+length){ 
                String word = s.substring(j, j+size); 
              
                if(!hashMap.containsKey(word) || tempMap.get(word) == 0){ 
                    break; 
                }  
                  
                else{ 
                    tempMap.put(word, tempMap.get(word) - 1); 
                    c--; 
                } 
                j += size; 
            } 
              
            if(c == 0){ 
                res.add(i); 
            } 
  
        } 
        return res; 
    } 
  
    public static void main(String[] args){ 
        String s = "capcodthecodcap"; 
        ArrayList<String> L = new ArrayList<>(Arrays.asList("cap", "cod")); 
        ArrayList<Integer> indices = Substring(s, L); 
        for(Integer i : indices){
            System.out.print(i+" "); 
        } 
    }
}
0 9

시간 복잡성 : O (nk) * k (n은 문자열의 길이, k는 모든 목록 단어가 연결된 후의 총 길이)

참조

링크드 인버퍼레딧텀블러
Translate »