სიმების შედარება, რომელიც შეიცავს ველურ ბარათებს


Რთული ტური Easy
ხშირად ეკითხებიან Accenture Amazon ოლა კაბინები
სიმებიანი

In სიმების შედარება, რომელიც შეიცავს ველურ ბარათებს პრობლემა, მეორე სიმები მივეცით მეორე სიმებიანი შეიცავს მცირე ანბანებს და პირველი შეიცავს მცირე ანბანებს და ველური ბარათების ზოგიერთ ნიმუშს. 

ველური ბარათების ნიმუშებია:

?: ამ ველური ბარათის შეცვლა შეგვიძლია ნებისმიერი პატარა ანბანით.

*: ამ ველური ბარათის შეცვლა შეგვიძლია ნებისმიერი სტრიქონით. დასაშვებია ცარიელი სტრიქონიც.

შეამოწმეთ, შესაძლებელია თუ არა პირველი სტრიქონის გადაქცევა მეორე სიმებად, ველური ბარათების შაბლონების ჩანაცვლებით.

მაგალითი

შეყვანის

xy * y?

xyyyxyx

გამოყვანის

True

განმარტება

სიმების შედარება, რომელიც შეიცავს ველურ ბარათებს

თუ * შეიცვალა yyx და? იცვლება x მაშინ ორივე სტრიქონი ერთნაირი ხდება.

რეკურსიული მიდგომა სიმების შედარებისთვის, რომელიც შეიცავს ველურ ბარათებს

საქმე 1: თუ პირველი სტრიქონის სიმბოლო ანბანია.

თუ ანბანი ორივე სტრიქონში ემთხვევა, მაშინ ვამოწმებთ მომდევნო სიმბოლოს ორივე სტრიქონში, თუ სხვას ვუბრუნებთ false.

საქმე 2: თუ პირველი სტრიქონის სიმბოლოა "?".

ჩვენ შეგვიძლია შევცვალოთ? მეორე სტრიქონში სიმბოლოთი. ასე რომ, ჩვენ ვამოწმებთ შემდეგ სიმბოლოს ორივე სტრიქონში.

საქმე 3: თუ პირველი სტრიქონის სიმბოლოა '*'.

ეს შეგვიძლია განვიხილოთ, როგორც ცარიელი სტრიქონი. ასე რომ, ჩვენ ვამოწმებთ პირველი სტრიქონის შემდეგ სიმბოლოს და მეორე სტრიქონის ამჟამინდელ სიმბოლოს.

OR

შეგვიძლია განვიხილოთ როგორც სიმებიანი, რომელიც შეიცავს სიმების ანალოგიურ სიმებს. ასე რომ, შეამოწმეთ პირველი სიმების მიმდინარე სიმბოლო და მეორე სიმების შემდეგი სიმბოლო.

განხორციელება

C ++ კოდი

#include <stdio.h> 
#include <stdbool.h> 
bool match(char *first, char * second) 
{ 
  if (*first == '\0' && *second == '\0') 
    return true; 
  if (*first == '*' && *(first+1) != '\0' && *second == '\0') 
    return false; 
  if (*first == '?' || *first == *second) 
    return match(first+1, second+1); 
  if (*first == '*') 
    return match(first+1, second) || match(first, second+1); 
  return false; 
} 
void test(char *first, char *second) 
{ match(first, second)? puts("Yes"): puts("No"); } 
int main() 
{ 
  test("xy*y?", "xyyyxyx"); 
  return 0; 
} 
Yes

ჯავის კოდი

class Check
{ 
static boolean match(String first, String second) 
{ 
  if (first.length() == 0 && second.length() == 0) 
    return true; 
  if (first.length() > 1 && first.charAt(0) == '*' && 
              second.length() == 0) 
    return false; 
  if ((first.length() > 1 && first.charAt(0) == '?') || 
    (first.length() != 0 && second.length() != 0 && 
    first.charAt(0) == second.charAt(0))) 
    return match(first.substring(1), 
          second.substring(1)); 
  if (first.length() > 0 && first.charAt(0) == '*') 
    return match(first.substring(1), second) || 
      match(first, second.substring(1)); 
  return false; 
} 
static void test(String first, String second) 
{ 
  if (match(first, second)) 
    System.out.println("Yes"); 
  else
    System.out.println("No"); 
} 
public static void main(String[] args) 
{ 
  test("xy*y?", "xyyyxyx"); 
  
}
Yes

დინამიური პროგრამირების მიდგომა სიმებიანი შედარებისთვის, რომელიც შეიცავს ველურ ბარათებს

რეკურსიული მიდგომა შეამოწმებს ყველა შესაძლო შემთხვევას. ქვე-პრობლემა ბევრჯერ გადაჭრილია ქვე-პრობლემასთან. ასე რომ, თავიდან ავიცილოთ თავიდან იგივე გამოთვლა, რომელიც გამოვიყენებთ დინამიური პროგრამირება. ქვე-პრობლემის შედეგს დავახსოვრებთ მას შემდეგ, რაც გამოვთვლით და პირდაპირ გამოვიყენებთ, როდესაც კიდევ ერთხელ უნდა გამოვთვალოთ. დროის სირთულე დინამიური პროგრამირება მიდგომა O (n * m)

განხორციელება

C ++ კოდი

#include <bits/stdc++.h> 
using namespace std; 
bool strmatch(char str[], char pattern[], 
      int n, int m) 
{ 

  if (m == 0) 
    return (n == 0); 
  bool lookup[n + 1][m + 1]; 
  memset(lookup, false, sizeof(lookup)); 
  lookup[0][0] = true; 
  for (int j = 1; j <= m; j++) 
    if (pattern[j - 1] == '*') 
      lookup[0][j] = lookup[0][j - 1]; 
  for (int i = 1; i <= n; i++) 
  { 
    for (int j = 1; j <= m; j++) 
    { 
      if (pattern[j - 1] == '*') 
        lookup[i][j] = lookup[i][j - 1] || 
              lookup[i - 1][j]; 
      else if (pattern[j - 1] == '?' || 
          str[i - 1] == pattern[j - 1]) 
        lookup[i][j] = lookup[i - 1][j - 1]; 
      else lookup[i][j] = false; 
    } 
  } 
  return lookup[n][m]; 
} 
int main() 
{ 
  char str[] = "xyyyxyx"; 
  char pattern[] = "xy*y?"; 
  if (strmatch(str, pattern, strlen(str), 
            strlen(pattern))) 
    cout << "Yes" << endl; 
  else
    cout << "No" << endl; 
  return 0; 
} 
Yes

ჯავის კოდი

import java.util.Arrays; 
public class check{   
  static boolean strmatch(String str, String pattern, 
                int n, int m) 
  { 
    if (m == 0) 
      return (n == 0); 
    boolean[][] lookup = new boolean[n + 1][m + 1]; 
    for(int i = 0; i < n + 1; i++) 
      Arrays.fill(lookup[i], false); 
    lookup[0][0] = true; 
    for (int j = 1; j <= m; j++) 
      if (pattern.charAt(j - 1) == '*') 
        lookup[0][j] = lookup[0][j - 1]; 
    for (int i = 1; i <= n; i++) 
    { 
      for (int j = 1; j <= m; j++) 
      { 
        if (pattern.charAt(j - 1) == '*') 
          lookup[i][j] = lookup[i][j - 1] || 
                lookup[i - 1][j]; 
        else if (pattern.charAt(j - 1) == '?' || 
          str.charAt(i - 1) == pattern.charAt(j - 1)) 
          lookup[i][j] = lookup[i - 1][j - 1]; 
        else lookup[i][j] = false; 
      } 
    } 
  
    return lookup[n][m]; 
  } 
  
  public static void main(String args[]) 
  { 
    String str = "xyyyxyx"; 
    String pattern = "xy*y?"; 
    if (strmatch(str, pattern, str.length(), 
              pattern.length())) 
      System.out.println("Yes"); 
    else
      System.out.println("No"); 
  
  } 
} 
Yes

სირთულის ანალიზი

დროის სირთულე: O (mxn)  სადაც n და m არის ორივე სიმების ზომა.

სივრცის სირთულე: O (mxn) სადაც n და m არის ორივე სიმების ზომა.

ლიტერატურა