Hackerrank - Common Child - Pavol Pidanič

Popis problému
Celý popis zadania sa nacháza – Hackerrank.

Riešenie
Implementácia je podľa algoritmu Longest Common Subsequence Problem.

Riešenie v ruby je implementované rovnakým spôsobom ako riešenie v Jave. Avšak jeden test v ruby mi neprešiel kvôli timeout.

Vytvoril som riešenie v týchto programovacích jazykoch:

Java
Ruby

Všetky riešenia sú dostupné aj na mojom GitHub profile.

Java

import java.util.Scanner;

public class CommonChild
{
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        String input1 = scanner.nextLine();
        String input2 = scanner.nextLine();

        int result = lcsOptimized(input1, input2);
        System.out.println(result);
        scanner.close();
    }

    private static int lcsOptimized(String input1, String input2)
    {
        int start = 0;
        int inEnd1 = input1.length() - 1;
        int inEnd2 = input2.length() - 1;

        while (start <= inEnd1 && start <= inEnd2
                && input1.charAt(start) == input2.charAt(start))
        {
            start++;
        }

        while (start <= inEnd1 && start <= inEnd2
                && input1.charAt(inEnd1) == input2.charAt(inEnd2))
        {
            inEnd1--;
            inEnd2--;
        }
        int[][] table = new int[inEnd1 - start + 1][inEnd2 - start + 1];
        for (int i = 0; i < table.length; i++)
        {
            for (int j = 0; j < table[i].length; j++)
            {
                table[i][j] = input1.length() - inEnd1 - 1;
            }
        }

        for (int i = start; i < inEnd1; i++)
        {
            for (int j = start; j < inEnd2; j++)
            {
                if(input1.charAt(i) == input2.charAt(j))
                {
                    table[i + 1][j + 1] = table[i][j] + 1;
                }
                else
                {
                    table[i + 1][j + 1] = table[i + 1][j] > table[i][j + 1] ? table[i + 1][j]
                            : table[i][j + 1];
                }
            }
        }

        return table[inEnd1][inEnd2];
    }
}

import java.util.Scanner;

public class CommonChild

{

public static void main(String[] args)

{

Scanner scanner = new Scanner(System.in);

String input1 = scanner.nextLine();

String input2 = scanner.nextLine();

int result = lcsOptimized(input1, input2);

System.out.println(result);

scanner.close();

}

private static int lcsOptimized(String input1, String input2)

{

int start = 0;

int inEnd1 = input1.length() - 1;

int inEnd2 = input2.length() - 1;

while (start <= inEnd1 && start <= inEnd2

&& input1.charAt(start) == input2.charAt(start))

{

start++;

}

while (start <= inEnd1 && start <= inEnd2

&& input1.charAt(inEnd1) == input2.charAt(inEnd2))

{

inEnd1--;

inEnd2--;

}

int[][] table = new int[inEnd1 - start + 1][inEnd2 - start + 1];

for (int i = 0; i < table.length; i++)

{

for (int j = 0; j < table[i].length; j++)

{

table[i][j] = input1.length() - inEnd1 - 1;

}

for (int i = start; i < inEnd1; i++)

{

for (int j = start; j < inEnd2; j++)

{

if(input1.charAt(i) == input2.charAt(j))

{

table[i + 1][j + 1] = table[i][j] + 1;

}

else

{

table[i + 1][j + 1] = table[i + 1][j] > table[i][j + 1] ? table[i + 1][j]

: table[i][j + 1];

}

return table[inEnd1][inEnd2];

}

Ruby

def lcs_length_optimized(input1, input2)
  start = 0
  m_end = input1.length - 1
  n_end = input2.length - 1
  while start <= m_end && start <= n_end && input1[start] == input2[start]
    start += 1
  end
  while start <= m_end && start <= n_end && input1[m_end] == input2[n_end]
    m_end -= 1
    n_end -= 1
  end
   
  table = Array.new(m_end - start + 1) { Array.new(n_end - start + 1,  (start - 0) + (input1.length - m_end - 1)) }
  
  for i in start...m_end do
    for j in start...n_end do
      if input1[i] == input2[j]
        table[i + 1][j + 1] = table[i][j] + 1
      else
        table[i + 1][j + 1] = [table[i + 1][j], table[i][j + 1]].max
      end
    end
  end
  return table[m_end][n_end]
end
       
def lcs_length(input1, input2)
  table = Array.new(input1.length + 1) { Array.new(input2.length + 1,  0) }
  
  input1.length.times do |i|
    input2.length.times do |j|
      if input1[i] == input2[j]
        table[i + 1][j + 1] = table[i][j] + 1
      else
        table[i + 1][j + 1] = [table[i + 1][j], table[i][j + 1]].max
      end
    end
  end
  return table[input1.length][input2.length]
end
    
input1 = gets.chomp
input2 = gets.chomp

puts lcs_length_optimized(input1, input2)

def lcs_length_optimized(input1, input2)

start = 0

m_end = input1.length - 1

n_end = input2.length - 1

while start <= m_end && start <= n_end && input1[start] == input2[start]

start += 1

end

while start <= m_end && start <= n_end && input1[m_end] == input2[n_end]

m_end -= 1

n_end -= 1

end

table = Array.new(m_end - start + 1) { Array.new(n_end - start + 1, (start - 0) + (input1.length - m_end - 1)) }

for i in start...m_end do

for j in start...n_end do

if input1[i] == input2[j]

table[i + 1][j + 1] = table[i][j] + 1

else

table[i + 1][j + 1] = [table[i + 1][j], table[i][j + 1]].max

end

return table[m_end][n_end]

end

def lcs_length(input1, input2)

table = Array.new(input1.length + 1) { Array.new(input2.length + 1, 0) }

input1.length.times do |i|

input2.length.times do |j|

if input1[i] == input2[j]

table[i + 1][j + 1] = table[i][j] + 1

else

table[i + 1][j + 1] = [table[i + 1][j], table[i][j + 1]].max

end

return table[input1.length][input2.length]

end

input1 = gets.chomp

input2 = gets.chomp

puts lcs_length_optimized(input1, input2)

Pavol Pidanič

Dokážem na 10 prstoch napočítať do 1023

Hackerrank – Common Child