연결된 문자열 목록이 회문을 형성하는지 확인

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 자본 하나 시스코 Facebook 구글 IXL Microsoft 뉴타 닉스 신탁 Paytm Snapchat 동네 짱 Yandex 주차
연결된 목록 연결 목록 조회수 279

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

"연결된 문자열 목록이 회문을 형성하는지 확인"문제에서 우리는 연결 목록 문자열 데이터 처리. 데이터가 회문을 형성하는지 여부를 확인하는 프로그램을 작성하십시오.

ba->c->d->ca->b
1

설명 : 위의 예에서 "bacdcab"문자열이 회문임을 알 수 있습니다.

접근

각 노드에 문자열이 포함 된 연결 목록이 제공됩니다. 연결 목록의 데이터가 회문을 형성하는지 확인해야합니다. 문자열은 회문 뒤로 읽는 것과 같은 앞으로 읽는 경우. 예를 들어 "bacdcab"이라는 숫자는 회문입니다. 연결 목록은 앞뒤로 이동할 때 요소 순서가 같으면 회문을 형성합니다.

암호알고리즘

  1. 빈 문자열을 초기화합니다.
  2. 연결 목록을 탐색하고 연결 목록의 모든 요소를 ​​해당 문자열에 저장합니다.
  3. 연결 목록을 탐색하여 각각의 첫 번째와 마지막 문자가 같은지 확인합니다. 어느 시점에서 그들이 같지 않으면 회문을 형성하지 않을 것입니다.

실시

링크 된 문자열 목록이 회문을 형성하는지 확인하는 C ++ 프로그램

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

class MyLinkedList {
public:
    struct ListNode {
        ListNode *next;
        string val;
        ListNode(string a): next(NULL), val(a){}
    };
    ListNode *head;

    MyLinkedList():head(NULL) {
    }
    
    void addAtHead(string val) {
        ListNode *node = new ListNode(val);
        node->next = head;
        head = node;
    }
    
    bool isPlalindrome(){
    	string str = "";
    	ListNode* ptr = head;
    	while(ptr){
    		str+=ptr->val;
    		ptr = ptr->next;
    	}
    	int n = str.size();
    	for(int i=0;i<n/2;i++){
    		if(str[i]!=str[n-i-1]){
    			return false;
    		}
    	}
    	return true;
    }

    void print_list(){
    	ListNode* node = head;
    while(node){
      cout<<node->val<<" ";
      node = node->next;
    }
        cout<<endl;
  }
};

int main(){
  MyLinkedList *list = new MyLinkedList();
  list->addAtHead("b");
  list->addAtHead("ca");
  list->addAtHead("d");
  list->addAtHead("c");
  list->addAtHead("ba");
  
  cout<<list->isPlalindrome();
}

링크 된 문자열 목록이 회문을 형성하는지 확인하는 Java 프로그램

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

public class Main{
  
  public static void main (String[] args) throws java.lang.Exception{
    
    MyLinkedList obj = new MyLinkedList();
    obj.addAtHead("b");
    obj.addAtHead("ca");
    obj.addAtHead("d");
    obj.addAtHead("c");
    obj.addAtHead("ba");
    
    System.out.println(obj.isPalindrome());
  }
  
  public static class MyLinkedList {
    
      class Node{
          Node next = null;
          String val = "";
          
          public Node(String val){
              this.val = val;
          }
      }
      
      private Node head;
      private int size;

      public MyLinkedList() {
          this.head = null;
          this.size = 0;
      }
      
      
      public void addAtHead(String val) {
          Node node = new Node(val);
          if(this.size == 0){
              this.head = node;
          }
          else{
              node.next = this.head;
              this.head = node;
          }
          this.size++;
      }
      
    public boolean isPalindrome(){
      String str="";
      Node curr = head;
      while(curr!=null){
        str+=curr.val;
        curr = curr.next;
      }
      
      int n = str.length();
      for(int i=0;i<n/2;i++){
        if(str.charAt(i)!=str.charAt(n-i-1)){
          return false;
        }
      }
      return true;
    }

    public void printList(){
      Node curr = head;
      while(curr!=null){
        System.out.print(curr.val+" ");
        curr = curr.next;
      }
      System.out.println("");
    }
      
  }
}
1

복잡성 분석

시간 복잡성

O (N) 어디에 n 주어진 연결 목록에있는 노드의 수입니다. 여기에서 문자열의 모든 값을 추가하고 해당 문자열에서 회문 조건을 확인합니다.

공간 복잡성

O (N) 주어진 줄이있는 목록의 모든 노드 값을 연결하여 형성된 문자열을 사용하기 때문입니다.

균열 시스템 설계 인터뷰
Translate »