የዱር ካርዶችን የያዘ ገመድ ንፅፅር  


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ Accenture አማዞን ኦላ ካብስ
ሕብረቁምፊ

In የዱር ካርዶችን የያዘ ገመድ ንፅፅር ችግር ፣ ሁለተኛ ሁለት ክሮች ሰጥተናል ክር አነስተኛ ፊደላትን ይ andል እና የመጀመሪያው ትናንሽ ፊደሎችን እና አንዳንድ የዱር ምልክት ቅጦችን ይ containsል ፡፡ 

የዱር ካርድ ቅጦች

?: ይህንን የዱር ምልክት በማንኛውም ትንሽ ፊደል መተካት እንችላለን።

*: ይህንን የዱር ካርድ በማንኛውም ገመድ መተካት እንችላለን። ባዶ ገመድም ይፈቀዳል።

የዱር ምልክት ንድፎችን በመተካት የመጀመሪያው ሕብረቁምፊ ወደ ሁለተኛው ሕብረቁምፊ ሊለወጥ እንደሚችል ያረጋግጡ።

ለምሳሌ  

ግቤት

xy * y?

xyyyxyx

ዉጤት

እርግጥ ነው

ማስረጃ

የዱር ካርዶችን የያዘ ገመድ ንፅፅር

* በ yyx ከተተካ እና? በ x ተተክቷል ከዚያ ሁለቱም ሕብረቁምፊዎች አንድ ይሆናሉ።

የዱር ካርዶችን የያዘ የሕብረ-ንፅፅር ተደጋጋሚ አቀራረብ  

መያዣ 1: በመጀመሪያው ሕብረቁምፊ ውስጥ አንድ ቁምፊ ፊደል ከሆነ.

በሁለቱም ሕብረቁምፊዎች ውስጥ ፊደሎች የሚዛመዱ ከሆነ ከዚያ እኛ በሌላ ሐረግ ውስጥ ቀጣዩን ገጸ-ባህሪ እንፈትሻለን በሌላ ሐሰት እንመልሳለን

መያዣ 2በመጀመሪያው ሕብረቁምፊ ውስጥ አንድ ቁምፊ ‹?› ከሆነ ፡፡

እኛ መተካት እንችላለን? በሁለተኛው ሕብረቁምፊ ውስጥ ካለው ቁምፊ ጋር። ስለዚህ በሁለቱም ሕብረቁምፊዎች ውስጥ ቀጣዩን ገጸ-ባህሪ እንፈትሻለን ፡፡

መያዣ 3: በመጀመሪያው ሕብረቁምፊ ውስጥ አንድ ቁምፊ '*' ከሆነ።

እንደ ባዶ ገመድ ልንቆጥረው እንችላለን ፡፡ ስለዚህ የመጀመሪያውን ሕብረቁምፊ እና የሁለተኛውን ሕብረቁምፊ የአሁኑን ገጸ-ባህሪ እንፈትሻለን ፡፡

OR

ከሁለተኛው ሕብረቁምፊ ጋር የሚመሳሰሉ ቁምፊዎችን የያዘ እንደ ገመድ ልንቆጥረው እንችላለን ፡፡ ስለዚህ የመጀመሪያውን ሕብረቁምፊ የአሁኑን ቁምፊ እና የሁለተኛውን ሕብረቁምፊ ቀጣይ ቁምፊ ያረጋግጡ።

አፈጻጸም

ሲ ++ ኮድ

#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

የዱር ካርዶችን ለያዘው ሕብረቁምፊ ንፅፅር ተለዋዋጭ የፕሮግራም አቀራረብ  

ተደጋጋሚ አቀራረብ ሁሉንም ሊሆኑ የሚችሉ ጉዳዮችን ይፈትሻል ፡፡ እዚህ ፣ ንዑስ ችግር ብዙ ጊዜ የተፈታ ንዑስ ችግርን ይጠራል ፡፡ ስለዚህ የምንጠቀምበትን ተመሳሳይ ንዑስ ችግር እንደገና ለማስላት ለማስቀረት ተለዋዋጭ ፕሮግራም. የአንድ ንዑስ ችግር ውጤትን አንዴ ከተሰላ በኋላ በማስታወስ እንደገና ማስላት ሲያስፈልገን በቀጥታ እንጠቀማለን ፡፡ የጊዜ ውስብስብነት እ.ኤ.አ. ተለዋዋጭ ፕሮግራም አቀራረብ ነው ኦ (n * m) ፡፡

ተመልከት
የተደረደረ ዝርዝርን ወደ ሁለትዮሽ ፍለጋ ዛፍ ይለውጡ

አፈጻጸም

ሲ ++ ኮድ

#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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት ኦ (mxn)  n እና m የት የሁለቱም ሕብረቁምፊዎች መጠኖች ናቸው።

ተመልከት
የቃላት ንድፍ

የቦታ ውስብስብነት: O (mxn) n እና m የት የሁለቱም ሕብረቁምፊዎች መጠኖች ናቸው።

ማጣቀሻዎች