Concatenando dos subcadenas para proporcionar la cadena palindrómica más grande posible -- java campo con performance campo con strings camp codereview Relacionados El problema

Concatenating two substrings to provide the largest possible palindromic string


2
vote

problema

Español

El código extrae dos subcadenas de diferentes cadenas y concatinándolos para proporcionar la cadena palindrómica más grande posible.

Objetivo:

Tienes dos cuerdas, (a) y (b). Encuentra una cadena, (c), tal que: (c) = (d) + (e).

(d), (e) se puede expresar como donde (D) es una subcadena no vacía de (a) y (e) es una subcadena no vacía de (b). (c) es una cadena palindrómica. La longitud de la mayor ya sea posible. Para cada uno de los pares de cuerdas. (a) y (b) recibidos como entrada, encontrar e imprimir cadena en una nueva línea. Si puede formar más de una cadena válida, imprima lo que sea Uno viene primero alfabéticamente. Si no hay respuesta válida, imprima -1 en vez.

¿Cómo puedo mejorar el rendimiento de este código, reduciendo el tiempo de compilación y manteniendo la funcionalidad igual?

  import java.io.*; import java.util.*;  public class Solution {     boolean isPalindrome(String s) {   int n = s.length();   for (int i=0;i<(n / 2);++i) {      if (s.charAt(i) != s.charAt(n - i - 1)) {          return false;      }   }    return true; }      public static void main(String[] args) {          String result="";          Scanner in = new Scanner(System.in);         int n = in.nextInt();         for(int a=0; a<n; a++)             {int length1, length2, i,c,d,j;         int max_length=0;         String string1 = in.next();         String sub1,sub2;         String string2 = in.next();         length2=string2.length();         length1 = string1.length();           for( c = 0 ; c <length1 ; c++ )       {          for( i = length1-c ; i >0 ; i-- )          {             sub1 = string1.substring(c, c+i);             for( d = 0 ; d < length2 ; d++ )       {          for( j = length2-d ; j >0 ; j-- )          {             sub2 = string2.substring(d, d+j);             String temp=sub1+sub2;               Solution obj= new Solution();              if(temp.length()>=max_length && obj.isPalindrome(temp)==true)                   {                  if (max_length==temp.length())                   {   if(temp.compareTo(result)<0)                      {                      result=temp;                   }}                  else {                      max_length=temp.length();                  result=temp;                   }              }          }       }          }       }              if(max_length==0)                  System.out.println(-1);              else                  {        System.out.println(result);              result="";              }         }    /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */     } }   
Original en ingles

The code extracts two substrings from different strings and concatinating them to provide the largest possible palindromic string.

Objective:

You have two strings, (a) and (b). Find a string, (c), such that: (c)=(d)+(e).

(d),(e) can be expressed as where (d) is a non-empty substring of (a) and (e) is a non-empty substring of (b). (c) is a palindromic string. The length of is as long as possible. For each of the pairs of strings (a) and (b) received as input, find and print string on a new line. If you're able to form more than one valid string , print whichever one comes first alphabetically. If there is no valid answer, print -1 instead.

How can I improve the performance of this code, reducing the compile time and keeping the functionality the same?

import java.io.*; import java.util.*;  public class Solution {     boolean isPalindrome(String s) {   int n = s.length();   for (int i=0;i<(n / 2);++i) {      if (s.charAt(i) != s.charAt(n - i - 1)) {          return false;      }   }    return true; }      public static void main(String[] args) {          String result="";          Scanner in = new Scanner(System.in);         int n = in.nextInt();         for(int a=0; a<n; a++)             {int length1, length2, i,c,d,j;         int max_length=0;         String string1 = in.next();         String sub1,sub2;         String string2 = in.next();         length2=string2.length();         length1 = string1.length();           for( c = 0 ; c <length1 ; c++ )       {          for( i = length1-c ; i >0 ; i-- )          {             sub1 = string1.substring(c, c+i);             for( d = 0 ; d < length2 ; d++ )       {          for( j = length2-d ; j >0 ; j-- )          {             sub2 = string2.substring(d, d+j);             String temp=sub1+sub2;               Solution obj= new Solution();              if(temp.length()>=max_length && obj.isPalindrome(temp)==true)                   {                  if (max_length==temp.length())                   {   if(temp.compareTo(result)<0)                      {                      result=temp;                   }}                  else {                      max_length=temp.length();                  result=temp;                   }              }          }       }          }       }              if(max_length==0)                  System.out.println(-1);              else                  {        System.out.println(result);              result="";              }         }    /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */     } } 
        
   
   

Lista de respuestas

1
 
vote

Tweak menor

      boolean isPalindrome(String s) {   int n = s.length();   for (int i=0;i<(n / 2);++i) {      if (s.charAt(i) != s.charAt(n - i - 1)) {          return false;      }   }   

Su sangría está en todo el mapa. Copiar / Pegar Error?

Más importante aún, puede ahorrar algunas matemáticas escribiendo esto

      public static boolean isPalindrome(String s) {         for (int i = 0, j = s.length() - 1; i < j; ++i, --j) {             if (s.charAt(i) != s.charAt(j)) {                 return false;             }         }          return true;     }   

Tal vez un buen compilador, optimizarlos, pero su original estaba haciendo cuatro operaciones matemáticas por iteración donde esto solo hace dos (y una declaración extra en). Tampoco contando las comparaciones.

Tweak pequeño

Reescribiría main como

          try (Scanner in = new Scanner(System.in))         {             for (int n = in.nextInt(); n > 0; n--)             {                 String string1 = in.next();                 String string2 = in.next();                  String palindrome = findLongestPalindrome(string1, string2);                 if (palindrome.isEmpty())                 {                     System.out.println(-1);                 }                 else                 {                     System.out.println(palindrome);                 }             }         }   

Poner el algoritmo en un método separado hace que sea más fácil probar y limpiar main por mucho.

No necesitamos una variable de bucle separada para los casos de prueba aquí. Si decidimos en lugar de incrementar, podemos simplificar esa lógica.

Poner el Scanner En un try -with-withits Elimina una advertencia de compilador sobre nunca cerrar el Scanner .

Tweaks principales

        for( c = 0 ; c <length1 ; c++ )       {          for( i = length1-c ; i >0 ; i-- )          {             sub1 = string1.substring(c, c+i);             for( d = 0 ; d < length2 ; d++ )       {          for( j = length2-d ; j >0 ; j-- )          {             sub2 = string2.substring(d, d+j);             String temp=sub1+sub2;               Solution obj= new Solution();              if(temp.length()>=max_length && obj.isPalindrome(temp)==true)                   {                  if (max_length==temp.length())                   {   if(temp.compareTo(result)<0)                      {                      result=temp;                   }}                  else {                      max_length=temp.length();                  result=temp;                   }              }          }       }          }       }   

Cambié a

      public static String findLongestPalindrome(String a, String b) {         String result = "";         for (int aStart = 0 ; aStart < a.length() ; aStart++ )         {             char firstLetter = a.charAt(aStart);             for (int bEnd = b.lastIndexOf(firstLetter); bEnd >= 0 ; bEnd = b.lastIndexOf(firstLetter, bEnd - 1) )             {                 for (int aEnd = a.length() ; aEnd > aStart ; aEnd-- )                 {                     String aSubstr = a.substring(aStart, aEnd);                     int requiredLength = Math.max(result.length() - aSubstr.length(), 0);                     for (int bStart = 0 ; bStart <= bEnd - requiredLength; bStart++ )                     {                         String candidate = aSubstr + b.substring(bStart, bEnd + 1);                          if (candidate.length() >= result.length() && isPalindrome(candidate))                         {                             if (candidate.length() == result.length() && candidate.compareTo(result) >= 0)                             {                                 continue;                             }                              result = candidate;                         }                     }                 }             }         }          return result;     }   

Nombres de parámetros arbitrarios cambiados para que coincidan con la declaración del problema.

Variables de índice de bucle modificados para que coincidan con su significado en relación con los parámetros.

Uso de public static boolean isPalindrome(String s) { for (int i = 0, j = s.length() - 1; i < j; ++i, --j) { if (s.charAt(i) != s.charAt(j)) { return false; } } return true; } 0 Para encontrar el punto final de la segunda cadena significa que podemos saltar muchas de las subcadenas que nunca funcionarán. El código original tuvo que tomar las subcadenas, únete a ellos, y luego verifique si el resultado es un palíndromo en todas las subcadenas. Esto se reduce a las posibles subcadenas posibles.

Determinar el public static boolean isPalindrome(String s) { for (int i = 0, j = s.length() - 1; i < j; ++i, --j) { if (s.charAt(i) != s.charAt(j)) { return false; } } return true; } 1 Nos permite omitir la unión y revisar las subestrucciones que son demasiado cortas para trabajar.

He declarado variables justo a tiempo para ser inicializado. Esto hace que sea más fácil ver lo que está sucediendo.

Un algoritmo alternativo

La solución de fuerza bruta obvia es verificar todos los puntos de inicio y final posibles para ambas cadenas. Usted optimizó esto comenzando con las subcadenas más largas posibles, y agregué ajustes para optimizar más. Pero en realidad creo que esa fue la forma equivocada de ir. Tenga en cuenta que aún tiene que iterar sobre cada letra para verificar si es un palíndromo. Puede guardar la comprobación de algunas de las subcadenas si integra el cheque de palíndromo con tomar las subcadenas. En lugar de cuatro bucles anidados con un cheque de tiempo lineal en el medio, podemos usar solo tres bucles anidados. Itera hasta la solución correcta en lugar de revisarla.

 

Minor tweak

    boolean isPalindrome(String s) {   int n = s.length();   for (int i=0;i<(n / 2);++i) {      if (s.charAt(i) != s.charAt(n - i - 1)) {          return false;      }   } 

Your indentation is all over the map. Copy/paste error?

More importantly, you can save some math by writing this

    public static boolean isPalindrome(String s) {         for (int i = 0, j = s.length() - 1; i < j; ++i, --j) {             if (s.charAt(i) != s.charAt(j)) {                 return false;             }         }          return true;     } 

Perhaps a good compiler would optimize them out, but your original was doing four math operations per iteration where this only does two (and an extra at declaration). Not counting the comparisons for either.

Small tweak

I'd rewrite main as

        try (Scanner in = new Scanner(System.in))         {             for (int n = in.nextInt(); n > 0; n--)             {                 String string1 = in.next();                 String string2 = in.next();                  String palindrome = findLongestPalindrome(string1, string2);                 if (palindrome.isEmpty())                 {                     System.out.println(-1);                 }                 else                 {                     System.out.println(palindrome);                 }             }         } 

Putting the algorithm in a separate method makes it easier to test and cleans up main by a lot.

We don't need a separate loop variable for the test cases here. If we decrement instead of increment, we can simplify that logic.

Putting the Scanner in a try-with-resources eliminates a compiler warning about never closing the Scanner.

Major tweaks

      for( c = 0 ; c <length1 ; c++ )       {          for( i = length1-c ; i >0 ; i-- )          {             sub1 = string1.substring(c, c+i);             for( d = 0 ; d < length2 ; d++ )       {          for( j = length2-d ; j >0 ; j-- )          {             sub2 = string2.substring(d, d+j);             String temp=sub1+sub2;               Solution obj= new Solution();              if(temp.length()>=max_length && obj.isPalindrome(temp)==true)                   {                  if (max_length==temp.length())                   {   if(temp.compareTo(result)<0)                      {                      result=temp;                   }}                  else {                      max_length=temp.length();                  result=temp;                   }              }          }       }          }       } 

I changed to

    public static String findLongestPalindrome(String a, String b) {         String result = "";         for (int aStart = 0 ; aStart < a.length() ; aStart++ )         {             char firstLetter = a.charAt(aStart);             for (int bEnd = b.lastIndexOf(firstLetter); bEnd >= 0 ; bEnd = b.lastIndexOf(firstLetter, bEnd - 1) )             {                 for (int aEnd = a.length() ; aEnd > aStart ; aEnd-- )                 {                     String aSubstr = a.substring(aStart, aEnd);                     int requiredLength = Math.max(result.length() - aSubstr.length(), 0);                     for (int bStart = 0 ; bStart <= bEnd - requiredLength; bStart++ )                     {                         String candidate = aSubstr + b.substring(bStart, bEnd + 1);                          if (candidate.length() >= result.length() && isPalindrome(candidate))                         {                             if (candidate.length() == result.length() && candidate.compareTo(result) >= 0)                             {                                 continue;                             }                              result = candidate;                         }                     }                 }             }         }          return result;     } 

Changed arbitrary parameter names to match the problem statement.

Changed loop index variables to match their meaning relative to the parameters.

Using lastIndexOf to find the endpoint of the second string means that we can skip a lot of substrings that will never work. The original code had to take the substrings, join them, and then check if the result is a palindrome on all substrings. This reduces down to only possible substrings.

Determining the requiredLength allows us to skip joining and checking substrings that are too short to work.

I declared variables just in time to be initialized. This makes it easier to see what's happening.

An alternative algorithm

The obvious brute force solution is to check every possible start and end points for both strings. You optimized this by starting with the longest possible substrings, and I added tweaks to optimize that more. But I actually think that was the wrong way to go. Note that you still have to iterate over every letter to check if it is a palindrome. You can save checking some of the substrings if you integrate the palindrome check with taking the substrings. Instead of four nested loops with a linear time check in the middle, we can use just three nested loops. Iterate up to the correct solution rather than check down to it.

 
 

Relacionados problema

11  Optimizando el corrector de anagramas Java (comparar 2 cadenas)  ( Optimizing java anagram checker compare 2 strings ) 
Un anagrama es como una mezcla de las letras en una cadena: pots es un anagrama de detener wilma es un anagrama de ilwma Estoy pasando por el ...

3  Implementación más portátil de Tolower ()  ( More portable tolower implementation ) 
Me estoy desafiando a intentar intentar escribir una función que sea tan eficiente, portátil y a prueba de fallas posible. La función es muy simple y solo con...

8  Conversión de STD :: Chrono :: Time_Point to / from std :: string  ( Converting stdchronotime point to from stdstring ) 
Considere estas funciones que permitan convertir checkOnline.sh4 a / FROM checkOnline.sh5 Con un formato Fecha de fecha ". checkOnline.sh6 con uso:...

6  Las vocales en una cadena están en orden alfabético  ( Vowels in a string are in alphabetical order ) 
Tarea Escriba una implementación que devuelva si un 99887776655544330 tiene vocales (idioma inglés) en orden alfabético (A-Z) o no. Feedback es mi v...

10  Función recursiva que genera las permutaciones de una cadena  ( Recursive function that generates the permutations of a string ) 
Estoy buscando una revisión de mi función recursiva que genere las permutaciones de una cadena. ¿Hay mejores formas de hacer esto? var permutations = []; ...

1  Compruebe si dos cadenas son permutación entre sí  ( Check if two strings are permutation of each other ) 
private String sort(String word) { char[] content = word.toCharArray(); Arrays.sort(content); return new String(content); } private boolea...

9  Convierta una contraseña a una cadena fonética para usuarios finales  ( Convert a password to a phonetic string for end users ) 
Tanto como lo odio, a veces proporcionar contraseñas a las personas debe hacerse electrónicamente. Cuando hago eso, trato de eliminar cualquier ambigüedad que...

2  Función para borrar un carácter en una cadena  ( Function to erase a character in a string ) 
void chrrem (char arr[], size_t len, size_t pos) { memmove(arr + pos, arr + (pos + 1), (len - pos) + 1); } Se supone que es simplemente rápido. Borra...

18  Invirtiendo una cadena  ( Reversing a string ) 
Tuve esto como una pregunta de entrevista, y el entrevistador señaló esto. Esto es lo que escribí: //C# Syntax here public string Reverse(string s) { c...

1  Imprima todos los tamaños posibles de subsecuencias de cadena en C  ( Print out all possible sizes of subsequences of string in c ) 
Por ejemplo, dada una cadena "abcdefghijk", quiero que mi función se imprima: a, b, c, d, e, f, g, h, i, j, k. ab, bc, cd, de, ef, fg, gh, hi, ij, jk ab...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos