지금 이 현재
GitHub
  • INTRO
  • CATEGORY
    • Java
      • JVM(Java Virtual Machine)
      • System.arraycopy()
      • toArray 함수 호출 시 빈 배열을 전달해야 하는 이유
      • POI Excel 인쇄 영역, 페이지 나누기 설정
      • Overloading & Overriding
      • Functional Interface
      • computeIfAbsent 메소드를 알아보자
    • Computer Science
      • 캐리지 리턴 문자('\r')
    • Kotlin
      • Java 와 다른 Kotlin
    • C++
      • ios_base::sync_with_stdio 의 역할과 사용 이유
    • Javascript
      • 자바스크립트 기본 - 문법
      • 자바스크립트 기본 - 함수
    • MySQL
      • EXPLAIN
    • Android
      • Android 기초
    • Error
      • macOS 업데이트 후 mysql 실행 에러
    • Algorithm
      • 모듈러 산술 (Modular Arithmetic)
  • BOOK
    • 헤드퍼스트 디자인 패턴
      • 전략 패턴(Strategy Pattern)
      • 옵저버 패턴(Observer Pattern)
      • 커맨드 패턴(Command Pattern)
      • 데코레이터 패턴(Decorator Pattern)
    • 자바의 정석
      • Chapter 14. Lambda & Stream
    • 함께 자라기
      • 자라기
  • STUDY
    • 99클럽
      • [99클럽 코테 스터디 1일차 TIL] 프로그래머스 - n^2 배열 자르기
      • [99클럽 코테 스터디 2일차 TIL] 프로그래머스 - x만큼 간격이 있는 n개의 숫자
      • [99클럽 코테 스터디 3일차 TIL] 프로그래머스 - 문자열 내 마음대로 정렬하기
      • [99클럽 코테 스터디 4일차 TIL] 프로그래머스 - JadenCase 문자열 만들기
      • [99클럽 코테 스터디 5일차 TIL] 프로그래머스 - 전화번호 목록
      • [99클럽 코테 스터디 6일차 TIL] 프로그래머스 - 의상
      • [99클럽 코테 스터디 7일차 TIL] 프로그래머스 - 하노이의 탑
      • [99클럽 코테 스터디 8일차 TIL] 프로그래머스 - 기능개발
      • [99클럽 코테 스터디 9일차 TIL] 프로그래머스 - 더 맵게
      • [99클럽 코테 스터디 10일차 TIL] 프로그래머스 - 이중우선순위큐
      • [99클럽 코테 스터디 11일차 TIL] 프로그래머스 - 카드 뭉치
      • [99클럽 코테 스터디 12일차 TIL] 프로그래머스 - H-Index
      • [99클럽 코테 스터디 13일차 TIL] 백준 - 숫자 카드
      • [99클럽 코테 스터디 14일차 TIL] 백준 - 숫자 카드 2
      • [99클럽 코테 스터디 15일차 TIL] LeetCode - Prefix and Suffix Search
      • [99클럽 코테 스터디 16일차 TIL] 프로그래머스 - 모음사전
      • [99클럽 코테 스터디 17일차 TIL] 백준 - 촌수계산
      • [99클럽 코테 스터디 18일차 TIL] 백준 - 단지번호붙이기
      • [99클럽 코테 스터디 19일차 TIL] 프로그래머스 - 구명보트
      • [99클럽 코테 스터디 20일차 TIL] 프로그래머스 - 큰 수 만들기
      • [99클럽 코테 스터디 21일차 TIL] 프로그래머스 - 피보나치 수
      • [99클럽 코테 스터디 22일차 TIL] 프로그래머스 - 멀리 뛰기
      • [99클럽 코테 스터디 23일차 TIL] 프로그래머스 - 마법의 엘리베이터
      • [99클럽 코테 스터디 24일차 TIL] 프로그래머스 - 대충 만든 자판
      • [99클럽 코테 스터디 29일차 TIL] LeetCode - Longest Increasing Subsequence
      • [99클럽 코테 스터디 31일차 TIL] 백준 - 점프 점프
      • [99클럽 코테 스터디 32일차 TIL] 프로그래머스 - 무인도 여행
      • [99클럽 코테 스터디 33일차 TIL] 프로그래머스 - 리코쳇 로봇
      • [99클럽 코테 스터디 34일차 TIL] 프로그래머스 - 타겟 넘버
      • [99클럽 코테 스터디 35일차 TIL] 프로그래머스 - 게임 맵 최단거리
      • [99클럽 코테 스터디 36일차 TIL] 프로그래머스 - 전력망을 둘로 나누기
      • [99클럽 코테 스터디 37일차 TIL] 백준 - 부등호
Powered by GitBook
On this page
  • 745. Prefix and Suffix Search
  • 문제 요약
  • 풀이 코드
  • 돌아보기
  • 다음에는
  1. STUDY
  2. 99클럽

[99클럽 코테 스터디 15일차 TIL] LeetCode - Prefix and Suffix Search

99클럽 코테 스터디 15일차 TIL 입니다.

Previous[99클럽 코테 스터디 14일차 TIL] 백준 - 숫자 카드 2Next[99클럽 코테 스터디 16일차 TIL] 프로그래머스 - 모음사전

Last updated 9 months ago

Hard


Design a special dictionary that searches the words in it by a prefix and a suffix.

Implement the WordFilter class:

  • WordFilter(string[] words) Initializes the object with the words in the dictionary.

  • f(string pref, string suff) Returns the index of the word in the dictionary, which has the prefix pref and the suffix suff. If there is more than one valid index, return the largest of them. If there is no such word in the dictionary, return -1.

Example 1:

Input
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
Output
[null, 0]
Explanation
WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); // return 0, because the word at index 0 has prefix = "a" and suffix = "e".

Constraints:

  • 1 <= words.length <= 104

  • 1 <= words[i].length <= 7

  • 1 <= pref.length, suff.length <= 7

  • words[i], pref and suff consist of lowercase English letters only.

  • At most 104 calls will be made to the function f.

문제 요약

주어진 문자열 배열에서 인수로 전달할 접두사와 접미사로 이루어진 문자열의 인덱스를 반환하는데 중복될 경우, 더 큰 인덱스 값을 반환하면 되는 문제입니다.


풀이 코드

class WordFilter {

    private final String[] words;

    public WordFilter(String[] words) {
        this.words = words;
    }
    
    public int f(String pref, String suff) {
        int idx = -1;
        for (int i = words.length - 1; i > -1; i--) {
            String word = words[i];
            if (word.charAt(0) != pref.charAt(0)) continue;
            if (word.startsWith(pref) && word.endsWith(suff)) {
                idx = i;
                break;
            }
        }
        return idx;
    }
}

/**
 * Your WordFilter object will be instantiated and called as such:
 * WordFilter obj = new WordFilter(words);
 * int param_1 = obj.f(pref,suff);
 */
  • Time: 1363 ms

  • Space: 57.7 MB

제한 사항이 문자열 배열의 크기가 최대 10만개까지여서 시간 초과로 계속 실패했다. 중복될 경우 더 큰 인덱스 값을 반환하면 되니까 일단 문자열 배열을 뒤에서부터 순회하도록 했다.

그래도 시간 초과가 떠서 문자열의 첫번째 문자와 접두사의 첫번째 문자가 다르면 비교할 의미가 없기 때문에 바로 continue 시켜주는 조건문을 작성하니까 정말 턱걸이로 통과했다.

해당 문제는 Trie 알고리즘을 활용하거나 HashMap 에 문자열에 대한 모든 접두사와 접미사 조합을 key 로 추가하는 방법도 있다.

두 방법에 대해선 스스로 더 공부한 후에 공유하도록 하겠다.


돌아보기

이중 반복문을 너무 배제시켰던 것 같다. 시간 복잡도를 생각하면서 풀어봐야겠다.

다음에는

  • 이중 for 문과 친해지기

  • 시간 복잡도도 생각하기

  • 자료구조 좀 활용하기


#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL

745. Prefix and Suffix Search