Tellərin K məsafədən ayrı olub olmadığını yoxlayın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Deutsche Bank Facebook GE Healthcare microsoft
Dinamik proqramlaşdırma Matris SimBaxılıb 357

Problem bəyanat

İki sətir və k tam ədədi verilərək verilmiş olub olmadığını yoxlamaq üçün bir proqram yazın strings bir-birindən k məsafədədir və ya deyil. Yəni hər hansı bir simvol uyğun gəlmirsə və ya hər hansı bir simvol götürülürsə, o zaman bir-birindən k məsafəsi kimi tanınır.

Giriş Formatı

Birinci sətirdə tam bir K dəyəri, ikinci və üçüncü sətirdə s1 (birinci sətir) və s2 (ikinci sətir) var.

Çıxış formatı

Çap et “TRUE”Əgər bu sətir bir-birindən k məsafədədirsə, əks halda“FALSE".

Məhdudiyyətlər

  • 1<= |S1|, |S2|<=10^3
  • Sətirdə yalnız kiçik hərflər var.

misal

2
cat
cade
TRUE

Dizələrin K məsafədən ayrı olub olmadığını yoxlamaq üçün alqoritm

  • Yuxarıdakı formatı izləyərək giriş edin.
  • Hər iki simli məsafəni tapın və aralarındakı fərqi yoxlayın. Fərq k çapdan böyükdürsə “FALSE".
  • (N + 1) * (m + 1) ölçülü bir dp matris yaradın və aşağıdan yuxarıya doğru doldurun.

1. Əgər s1 uzunluğu sıfırsa, ikinci sətrin bütün simvollarını daxil edin.

2. Əgər s2-nin uzunluğu sıfırsa, onda ikinci sətrin bütün simvollarını silin.

3. Son simvollar eynidirsə, son işarəni görməyin və qalan simli üçün təkrarlayın.

4. Son xarakter fərqlidirsə, bütün imkanları nəzərdən keçirin və minimumu tapın.

  • Dp [n] [m] dəyəri k-dən az və ya bərabərdirsə, “yazdırınTRUE”Əks halda“FALSE".

Həyata keçirilməsi

İplərin K məsafədən ayrı olub olmadığını yoxlamaq üçün C ++ proqramı

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int k;
    cin>>k;
    string s1,s2;
    cin>>s1>>s2;
    int n=s1.length();
    int m=s2.length();
    if(abs(n-m)>k)
    {
        cout<<"FALSE"<<endl;
    }
    else
    {
        int dp[n+1][m+1];
        for(int i=0;i<=m;i++)
        {
            dp[0][i]=i;
        }
        for(int i=0;i<=n;i++)
        {
            dp[i][0]=i;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(s1[i-1]==s2[j-1])
                {
                    dp[i][j]=dp[i-1][j-1];
                }
                else
                {
                    dp[i][j]= 1 + min(dp[i][j - 1], min(dp[i - 1][j], dp[i - 1][j - 1]));
                }
            }
        }
        if(dp[n][m]<=k)
        {
            cout<<"TRUE"<<endl;
        }
        else
        {
            cout<<"FALSE"<<endl;
        }
    }
}

Dizələrin K məsafədən ayrı olub olmadığını yoxlamaq üçün Java proqramı

import java.util.Scanner;

class sum { 
    public static void main(String[] args) 
    {
        Scanner sr= new Scanner(System.in);
        int k = sr.nextInt();
        String s1= sr.next();
        String s2= sr.next();
        int n = s1.length(); 
        int m = s2.length();
        if(Math.abs(m-n)>k)
        {
            System.out.println("FALSE");
        }
        else
        {
            int dp[][] = new int[n+1][m+1];
            for(int i=0;i<=m;i++)
            {
                dp[0][i]=i;
            }
            for(int i=0;i<=n;i++)
            {
                dp[i][0]=i;
            }
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                {
                    if(s1.charAt(i-1)==s2.charAt(j-1))
                    {
                        dp[i][j]=dp[i-1][j-1];
                    }
                    else
                    {
                        dp[i][j]= 1 + Math.min(dp[i][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j - 1]));
                    }
                }
            }
            if(dp[n][m]<=k)
            {
                System.out.println("TRUE");
            }
            else
            {
                System.out.println("FALSE");
            }
            }
    } 
}
4
TutorialCup
TutorCup
TRUE

İplərin K məsafədən ayrı olub olmadığını yoxlamaq üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n * m) burada n birinci telin ölçüsü, m isə ikinci simin ölçüsüdür. Burada dp ölçüsünü (n + 1) * (m + 1) aşağıdan yuxarıya doldururuq.

Kosmik Mürəkkəblik

O (n * m) burada n birinci telin ölçüsü, m isə ikinci simin ölçüsüdür. Nəticəni burada tapmaq üçün dp matrisindən istifadə edirik.

arayış

Translate »